【二叉树专题】543. 二叉树的直径

共以下 16 个回答

• 岱 永久会员 2025年1月10日 下午2:19

  543. 二叉树的直径

  class Solution {
      int ans=0;
      public int diameterOfBinaryTree(TreeNode root) {
          if(root == null) return 0;
          depth(root);
          return ans;
      }
  
      public int depth(TreeNode node){
          if(node == null) return 0;
          int left = depth(node.left);
          int right = depth(node.right);
          ans= Math.max(ans,left+right);
          return Math.max(left,right)+1;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• mpweixin用户 普通 2024年12月24日 下午10:25

  class Solution {
  public:
          int result = 0;
          int depth(TreeNode* root){
              if(root == NULL) return 0;
              int left = depth(root->left);
              int right = depth(root->right);
              result = max(left+right, result);
              return max(left, right) +1;
          }
      int diameterOfBinaryTree(TreeNode* root) {
          depth(root);
          return result;
      }
  };
  

  实际上相当于从根节点左子树最深处走到根节点再到右子树最深点，即result=左树高+右树高

  0 赞同 0 条回复

  登录以回复
• 陆狗陆狗 普通 2024年12月8日 下午9:41

  解题思路
  – 某一个节点作为顶点时候的路径（直径）= 左子树的高度+右子树的高度
  – 只需要新建1个求高度的函数，1个遍历全部节点的递归过程中（把全局变量值直径记录下来）

  【题解1】不建议，展示的是最直观的思路

  class Solution {
      int maxDiamater=0;
      public int diameterOfBinaryTree(TreeNode root) {
          if(root==null){
              return 0;
          }
          f(root);
          return maxDiamater;
      }
  
      // 计算一个二叉树的深度
      public int depth(TreeNode root){
          if(root==null){
              return 0;
          }
          return Math.max(depth(root.left),depth(root.right))+1;
      }
  
      // 遍历二叉树，并在过程中把maxDiamater进行更新
      public void f(TreeNode root){
          if(root==null){
             return;
          }
          // 当前节点计算直径
          int nowDiamater= depth(root.left)+depth(root.right);
          maxDiamater=Math.max(nowDiamater,maxDiamater);
          // 左右节点的直径计算
          f(root.left);
          f(root.right);
      }
  }
  

  【题解2】建议，改进点就是在计算二叉树的深度时，(顺便借助这个遍历)去求出直径，这样就不需要二次遍历了

  class Solution {
      int maxDiamater=0;
      public int diameterOfBinaryTree(TreeNode root) {
          if(root==null){
              return 0;
          }
          depth(root);
          return maxDiamater;
      }
  
      // 计算一个二叉树的深度
      // 为了减少遍历的过程，我们需要在计算二叉树深度的时候，顺便求出maxDiamater,
      // 因为在计算二叉树的深度时，一定会遍历所有节点
      public int depth(TreeNode root){
          if(root==null){
              return 0;
          }
          // 正常计算高度
          int leftDepth= depth(root.left);
          int rightDepth= depth(root.right);
          int rootDepth= Math.max(leftDepth,rightDepth)+1;
          // (顺便)计算高度的遍历过程中去求出直径，这个是最好的优化
          int nowDiamater=leftDepth+rightDepth;
          maxDiamater=Math.max(nowDiamater,maxDiamater);
  
          return rootDepth;
      }
  
  }
  

  0 赞同 0 条回复

  登录以回复
• 黑键〰 普通 2024年12月5日 下午4:54

  /**
   * Definition for a binary tree node.
   * function TreeNode(val, left, right) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.left = (left===undefined ? null : left)
   *     this.right = (right===undefined ? null : right)
   * }
   */
  /**
   * @param {TreeNode} root
   * @return {number}
   */
  var diameterOfBinaryTree = function (root) {
      // 递归找左右子树最大深度
      if (root == null) return 0
      let deep = 0
      const findDeep = (root) => {
          if (root == null) return -1
          let l = 0
          let r = 0
          l = findDeep(root.left) + 1
          r = findDeep(root.right) + 1
          // 当前最大左右深度和，与新的左右深度和，比较
          deep = Math.max(deep, l + r)
          return Math.max(l, r)
      }
      findDeep(root)
      return deep
  };
  

  思路：对左右子树分别递归，注意求和的时候深度要记得+1才包含了子树到父节点的那个深度

  0 赞同 0 条回复

  登录以回复
• 晓宇 普通 2024年12月4日 下午9:04

  class Solution {
  public:
      int ans = 0; // 定义全局变量，存储最大直径
      int depth(TreeNode* root){
          if(root == nullptr) return 0;
          int lef_num = depth(root->left);  // 左子树最长边
          int rit_num = depth(root->right);  // 右子树最长边
          ans = max(ans, lef_num + rit_num);  // 最长边数等于节点数-1
          return max(lef_num,rit_num) + 1;  // 返回包含子树的最长节点数
      }
  
  
      int diameterOfBinaryTree(TreeNode* root) {
          depth(root);
          return ans;
  
      }
  };
  // 时间复杂度 o(n); 空间复杂度 o(lg(n^2))
  

  0 赞同 0 条回复

  登录以回复
• 苯庸 普通 2024年12月4日 下午7:26

  class Solution { // 中序
  int res = 0;
  public int diameterOfBinaryTree(TreeNode root) {
  solve(root);
  return res;
  }

  int solve(TreeNode root){
      if(root == null){
          return 0;
      }
      int left =  solve(root.left);
      int right = solve(root.right);
      res = Math.max(left + right, res);
      return Math.max(left, right) + 1;
  }
  

  }
  时间：O（n）
  空间：O（n）

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月4日 下午5:02

  class Solution {
      int res;
      int depth(TreeNode* root){
          if (root == NULL) {
              return 0;
          }
          int L = depth(root->left);
          int R = depth(root->right);
          res = max(res, L + R);
          return max(L, R) + 1;
      }
  public:
      int diameterOfBinaryTree(TreeNode* root) {
          depth(root);
          return res;
      }
  };
  

  经过当前节点的直径为其左子树深度与右子树深度相加。可以在递归求解二叉树深度时，定义全局变量保存直径的最大值。
  时间复杂度O(N)，空间复杂度O(N)。

  0 赞同 0 条回复

  登录以回复
• Kisara 普通 2024年12月4日 下午2:49

  直径就是左右深度相加

  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      int maxDiameter = 0;  // 记录全局的最大直径
  
      public int diameterOfBinaryTree(TreeNode root) {
          solve(root);  // 调用递归方法计算直径
          return maxDiameter;  // 返回最大直径
      }
  
      public int solve(TreeNode root) {
          if (root == null) return 0;  // 如果节点为空，返回 0
  
          // 递归计算左子树和右子树的深度
          int leftDepth = solve(root.left);
          int rightDepth = solve(root.right);
  
          // 更新最大直径，左子树深度 + 右子树深度
          maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
  
          // 返回当前节点的深度
          return Math.max(leftDepth, rightDepth) + 1;
      }
  }
  
  

  on on

  0 赞同 0 条回复

  登录以回复
• Renasc 普通 2024年12月4日 下午2:40

  时间复杂度O(n)，空间复杂度O(h)

  class Solution {
      // 定义全局变量，记录树的最长节点数
      int ans;
      public int diameterOfBinaryTree(TreeNode root) {
          ans = 1;
          depth(root);    // 数的最长节点数
          return ans - 1; // 树的边长等于节点数-1
      }
  
      public int depth(TreeNode root) {
          if (root == null) return 0;
  
          int L= depth(root.left); // 左子树的最长节点
          int R = depth(root.right); // 右子树的最长节点
          ans = Math.max(ans, L + R + 1); // 更新整个树的最长节点
          return Math.max(L, R) + 1;  // 返回包含单一子树的最长节点
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Xiang. 永久会员 2024年12月4日 下午12:35

  思路：在求最大深度的基础下，加上max全局变量，遍历每个结点的左右分支深度和的最大值即为最大直径（也就是最长的最短路径）
  class Solution {
       int max=1;
      public int diameterOfBinaryTree(TreeNode root){
          depth(root);
          return max-1;
  
      }
      public int depth(TreeNode root){
          if(root==null) return 0;
          int depthL=depth(root.left);
          int depthR=depth(root.right);
          int res=Math.max(depthR,depthL)+1;
          max=Math.max(max,depthL+depthR+1);
          return res;
      }
  }
  时间复杂度：o(n)
  空间复杂度：o(n)
  

  0 赞同 0 条回复

  登录以回复
• lQl 永久会员 2024年12月3日 下午10:24

  时间复杂度：O(n)
  空间复杂度：O(n)

  class Solution {
      public int ans = 0;
  
      public int diameterOfBinaryTree(TreeNode root) {
          depth(root);
          return ans;
      }
  
      public int depth(TreeNode root) {
          if (root == null)
              return 0;
          int left_depth = depth(root.left);
          int right_depth = depth(root.right);
          ans = Math.max(ans, left_depth + right_depth);
          return Math.max(left_depth, right_depth) + 1;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• jaron 普通 2024年12月3日 下午10:16

  LCR 175. 计算二叉树的深度 – 力扣（LeetCode）的变形，主要是理解题意：经过某一个节点的最长路径 = 左树深度 + 右树深度

  class Solution {
      static int ans;
  
      public int diameterOfBinaryTree(TreeNode root) {
          ans = 0;
          depth(root);
          return ans;
      }
  
      public int depth(TreeNode root) {
          if (root == null) {
              return 0;
          }
          int left = depth(root.left);
          int right = depth(root.right);
          // 经过某一个节点的最长路径 = 左树深度 + 右树深度
          ans = Math.max(left + right, ans);
          return Math.max(left, right) + 1;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 秋山丽奈 普通 2024年12月3日 下午8:50

  思路： 计算左右子树直径

  class Solution {
      private int ans = -1;
  
      public int diameterOfBinaryTree(TreeNode root) {
          dfs(root);
          return ans;
      }
  
      private int dfs(TreeNode node) {
          if (node == null) {
              // 与 +1 相抵消 
              return -1;
          }
  
          // 左子树最大长度 
          int lLen = dfs(node.left); 
          // 右子树最大长度 
          int rLen = dfs(node.right); 
  
          ans = Math.max(ans, lLen + rLen + 2); 
          // 当前子树最大链长
          return Math.max(lLen+1, rLen+1); 
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 迢迢星野 普通 2024年12月3日 下午8:33

  class Solution {
  
      public int diameterOfBinaryTree(TreeNode root) {
          // 方法一：求出左右子树的最大深度，相加即可
          // maxDepth(root);
          // 方法二：计算左右子树到当前节点的最大链长，并在此过程中更新所求的最大直径
          dfs(root);
          return maxDiameter;
      }
  
      int maxDiameter = 0;
  
      private int maxDepth(TreeNode root) {
          if (root == null) {
              return 0;
          }
  
          // 计算左右子树的最大深度
          int left = maxDepth(root.left);
          int right = maxDepth(root.right);
  
          // 计算最大直径
          maxDiameter = Math.max(maxDiameter, left + right);
  
          // 返回当前节点的最大深度
          return 1 + Math.max(left, right);
      }
  
      private int dfs(TreeNode root) {
          // 叶子节点的链长为 0，那么叶子节点的子节点的链长就是 -1
          if (root == null) {
              return -1;
          }
  
          // 计算当前节点到其左右子树的链长，+1 表示的左右子树根节点到当前节点的边
          int left = dfs(root.left) + 1;
          int right = dfs(root.right) + 1;
  
          // 比较出当前节点的最大直径
          maxDiameter = Math.max(maxDiameter, left + right);
  
          // 返回当前节点的最大链长
          return Math.max(left, right);
      }
  }
  

  思路：一个方法是根据二叉树的左右子树的最大高度进行计算，一个是根据左右子树到当前节点的最长链长进行计算。
  时间复杂度：O(n)
  空间复杂度：O(n)

  0 赞同 0 条回复

  登录以回复
• Jerry 普通 2024年12月3日 下午8:06

  class Solution {
  public:
      int res = INT_MIN;
      int diameterOfBinaryTree(TreeNode* root) {
          int tmp = diameterOfBinaryTreeHelper(root);
          return res==INT_MIN ? 0:res;
      }
      int diameterOfBinaryTreeHelper(TreeNode* root){
          if(!root) return 0;
          int curmax = 0;
          int leftmax = diameterOfBinaryTreeHelper(root->left);
          curmax  = curmax + leftmax;
          int rightmax = diameterOfBinaryTreeHelper(root->right);
          curmax  = curmax + rightmax;
          res = max(res, curmax);
  
          return max(leftmax, rightmax)+1;
      }
  };
  

  时间o(n)
  空间o(n)

  0 赞同 0 条回复

  登录以回复
• 月下足迹 普通 2024年12月3日 下午8:05

  //递归遍历二叉树

  class Solution {
  private int maxDiameter = 0;
  public int diameterOfBinaryTree(TreeNode root) {
  depth(root);
  return maxDiameter;
  }

  public int depth(TreeNode root) {
      if (root == null) return 0;
  
      int leftDepth = depth(root.left);
      int rightDepth = depth(root.right);
  
      maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
  
      return Math.max(leftDepth, rightDepth) + 1;
  }
  

  }

  0 赞同 0 条回复

  登录以回复