Gg 普通 2023年3月30日下午8:21

class Solution {

    private int max;

    public int diameterOfBinaryTree(TreeNode root) {
        helper(root);
        return max;
    }

    private int helper(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        // 直径等于左右子树高度和
        max = Math.max(left+right,max);
        return Math.max(left,right)+1;

    }
}

0 赞同 0 条回复

宁永久会员 2023年3月15日下午4:22

遍历过程中更新最大值

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        //最长路径是左子树加上右子树的高度，但是注意不一定从根节点出发。
        getHeight(root);
        return max;
    }
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        //计算高度的逻辑是左右子树取最大值+1
        int res = Math.max(left, right) + 1;
        //计算直径的逻辑是左右子树高度相加
        max = Math.max(left + right, max);
        return res;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月7日下午3:23

求高度顺便更新一下最大值

时间复杂度 O(N)
空间复杂度 O(H) H为树的最大深度

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return max;
    }
    private int height(TreeNode root) {
        if (root == null) return 0;
        int l = height(root.left);
        int r = height(root.right);
        max = Math.max(max, l + r);
        return Math.max(l, r) + 1;
    }
}

0 赞同 0 条回复

cute. 普通 2023年1月4日下午11:45

var diameterOfBinaryTree = function (root) {
  let maxDiameter = 0;
  const dfs = (root) => {
    // 访问到空节点了，返回0
    if (root == null) return 0;
    // 左子树为根的子树的的深度
    let leftMax = dfs(root.left);
    let rightMax = dfs(root.right);
    maxDiameter = Math.max(maxDiameter, leftMax + rightMax);
    // 返回该节点为根的子树的的深度
    return Math.max(leftMax, rightMax) + 1;
  };
  dfs(root);
  return maxDiameter;
};

时间复杂度:O(n)
空间复杂度:O(h)【h表示树的深度】

0 赞同 0 条回复

🚲南下普通 2022年12月2日上午11:53

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(root==nullptr) return 0;
        dfs(root);
        return maxvalue;
    }
    int maxvalue = 0;

    int dfs(TreeNode* root){ //递归解法
        if(root->left==nullptr&&root->right==nullptr) return 0;

        int leftsize = root->left==nullptr?0:dfs(root->left)+1; //左子树的深度
        int rightsize = root->right==nullptr?0:dfs(root->right)+1;//右子树的深度
        maxvalue = max(maxvalue,leftsize+rightsize); //更新maxvalue值
        return max(leftsize,rightsize); //返回到上一级
    }
};

0 赞同 0 条回复

symbol 普通 2022年11月27日上午11:48

 //var res int 很奇怪不能定义全局变量保存答案
func diameterOfBinaryTree(root *TreeNode) int {
    var help func(root *TreeNode) int
    res := 0
    if root == nil{
        return 0
    }

    help = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        left_h := help(root.Left) // 左子树最大深度
        right_h := help(root.Right) //右子树最大深度
        res = max(res, left_h + right_h) //每遍历一个节点 更新整个树的最大直径
        return max(left_h, right_h) + 1 //返回最大子树深度 + 1
    }
    help(root)
    return res
}
func max(a, b int) int {
    if a > b{
        return a
    }
    return b
}

0 赞同 0 条回复

xye 普通 2022年11月19日下午8:15

var maxd int
func diameterOfBinaryTree(root *TreeNode) int {
    maxd = 0
    depth(root)
    return maxd
}

func depth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := depth(root.Left)
    right := depth(root.Right)
    //以此节点为根结点的树的直径 跟 已知最大直径相比取较大
    maxd = max(left+right, maxd)
    //返回此节点的深度
    return max(left, right) + 1
}

func max(i int, j int) int {
    if i > j {
        return i
    }
    return j
}

时间O(n) 空间O(height)

0 赞同 0 条回复

浅夏的无奈普通 2022年11月13日下午5:20

时间复杂度：O(n)
空间复杂度：O(height),递归深度（栈空间）

class Solution {
    int val = 0;
    public int diameterOfBinaryTree(TreeNode root) {

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

0 赞同 0 条回复

yanshuojune 普通 2022年11月13日上午11:59

解题思路：二叉树的直径等于左子节点和右子节点的深度之和加一，递归遍历所有节点，找到最大直径节点；
时间复杂度：O(n)
空间复杂度：O(height),递归深度（栈空间）

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = -inf
        # 递归求解每个节点左右子节点的深度，相加减一即为该节点的直径
        def depth(node):
            if not node:
                return 0
            # 左、右子树的深度
            L = depth(node.left)
            R = depth(node.right)
            # 更新节点最大深度
            self.max_diameter = max(self.max_diameter, L + R + 1)
            # 计算该节点为根的子树的深度
            return max(L, R) + 1

        depth(root)
        return self.max_diameter - 1

0 赞同 0 条回复

黎昕普通 2022年11月11日下午8:17

时间 O(n)
空间 O(height) 如果计算递归栈的空间不计算栈的空间应该是 O(1)

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 思路：需要一个计算树深度的函数，需要深度优先遍历树的每一个节点，比较每一个节点的左右子树深度信息
        # 如果是这样的话，有很多重复的扫描，有没有可能时间复杂度更小
        # 如果维护一个类变量，使用递归方式的过程中，只需要遍历一遍就可以，在递归到下面的时候判断就可以
        res=0
        def depth(root):
            if not root:
                return 0
            nonlocal res
            leftdepth=depth(root.left)
            rightdepth=depth(root.right)
            res=max(res,leftdepth+rightdepth+1)
            return max(leftdepth,rightdepth)+1
        depth(root)
        return res-1

0 赞同 0 条回复

小肸永久会员 2022年11月11日下午5:03

思路：这题要找二叉树以每一个节点为起点的最长路径，路径的长度就是以这条路径中的根节点的左右子树的深度之和。写一个求root节点深度的函数，函数中更新res就行。时间复杂度为O(N)，空间复杂度为O(height)。

class Solution {
    private int res = -1;
    public int diameterOfBinaryTree(TreeNode root) {
        getDepth(root);
        return res;
    }
    private int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        res = Math.max(res, leftDepth + rightDepth);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月10日下午11:22

 //使用dfs 遍历每一个节点 以每个节点为中心点计算直径
    //时间复杂度O(n)
    //空间复杂度O(height)//height 为树的高度
    int res;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        dfs(root);
        return  res;
    }
    private int dfs(TreeNode node){
        if(node.left==null&&node.right==null) return 0;
        int left  =node.left==null?0:dfs(node.left)+1;
        int right  =node.right==null?0:dfs(node.right)+1;
        res=Math.max(res,left+right);
        return Math.max(left,right);
    }

0 赞同 0 条回复

刺猬普通 2022年11月10日下午4:35

class Solution {
public:
    int res = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return res;
    }
    int dfs(TreeNode* root) {
        if(root == nullptr)
            return 0;
        int lefth = dfs(root->left);
        int righth = dfs(root->right);
        res = res > (lefth + righth) ? res : (lefth + righth);
        return max(lefth, righth) + 1;
    }
};

时间空间复杂度都是O(N)

0 赞同 0 条回复

@ 普通 2022年11月9日上午11:32

思路：深度优先搜索，然后回溯的时候记录每一个根节点的最大路径
时间复杂度：O(N)，其中N为二叉树的节点数
空间复杂度：O(Height)，其中 Height为二叉树的高度

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

0 赞同 0 条回复

酥合普通 2022年11月8日下午9:32

/**
 * 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 {
    private int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return ans;
    }

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

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

0 赞同 0 条回复

马啸天永久会员 2022年11月7日下午3:38

  int ans;

    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }

    public int depth(TreeNode node) {
        if (node == null) {
            return 0;//访问到空节点，返回0
        }
        int L = depth(node.left);//左儿子为根的子树的深度
        int R = depth(node.right);//右儿子为根的子树的深度
        ans = Math.max(ans , L + R + 1);//计算d_node即L+R+1并更新ans
        return Math.max(L , R) + 1;//返回该节点为根的子树的深度

    }

0 赞同 0 条回复

lobort 普通 2022年11月5日下午6:51

class Solution {
    int maxL;
    public int diameterOfBinaryTree(TreeNode root) {
        maxL = 1;
        depth(root);
        return maxL - 1;
    }
    //层次优先遍历
    public int depth(TreeNode root){
        if(root == null ){
            return 0;
        }
        int L = depth(root.right);
        int R = depth(root.left);
        maxL = Math.max(maxL, L + R + 1);
        return Math.max(L, R) + 1;
    }
 //1、最大直径不过头节点
    //2、最大直接过头节点 
    // 设置函数向左右孩子要 左右孩子的最大直径 和 最大高度
    //最后比较左右最大直径  左右高度之和 比较
    public int diameterOfBinaryTree(TreeNode root) {
        return process(root).maxDistance;
    }
    public static  class Info{
        public int maxDistance;
        public int height;
        public Info(int m, int h){
            maxDistance = m;
            height = h;
        }
    }
    public static Info process(TreeNode root){
        if(root == null){
            return new Info(0, 0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int p1 = Math.max(leftInfo.maxDistance, rightInfo.maxDistance);
        int p2 = leftInfo.height + rightInfo.height;
        int maxDistance = Math.max(p1, p2);
        return new Info(maxDistance, height);
}

1 赞同 0 条回复

你有点可爱喔普通 2022年11月5日上午11:05

解题思路：该题是求出直径，也就是说一个路径下一定会有最近的父公共节点，那么路径长度=左子树深度+右子树深度。这里还有一点就是可以任意左右子树先遍历，可以采用深度优先搜索的方式。
时间复杂度：O(N）递归求深度，每个节点只访问一次
空间复杂度：树的高度，

  class Solution {
        int num;

        public int diameterOfBinaryTree(TreeNode root) {
            //深度计算
            Depth(root);
            return num;
        }

        int Depth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int L = Depth(root.left);
            int R = Depth(root.right);
            num = Math.max(num, L + R);
            return Math.max(L, R) + 1;
        }
    }

0 赞同 0 条回复

just 普通 2022年11月5日上午10:46

//一个值得注意的点是未必要经过根节点
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res;
int fun(TreeNode root){
if(! root) return 0;
int l=fun(root->left);
int r=fun(root->right);
res=max(res,l+r);
return 1+max(l,r);

}
int diameterOfBinaryTree(TreeNode* root) {
    res=0;
    fun(root);
    return res;

}

};

0 赞同 0 条回复

阿白普通 2022年11月5日上午10:37

1、求每个子树作为根的最大路径
2、时间O（n），空间O（n）

class Solution {
    int ans = 0;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr)
            return 0;
        findHeight(root);
        return ans;
    }
    int findHeight(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        int leftHeight = findHeight(root->left);
        int rightHeight = findHeight(root->right);
        int ret = std::max(leftHeight, rightHeight) + 1;
        ans = std::max(leftHeight + rightHeight, ans);
        return ret;
    }
};

0 赞同 0 条回复

天然普通 2022年11月4日下午8:56

想到了用递归求深度，但是在100/104就过不去了，还是整体思路有问题，递归！！！
时间空间复杂度O（n)

class Solution:

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.index = 1
        def depth(root):
            if not root: return 0
            l = depth(root.left)
            r = depth(root.right)
            self.index = max(self.index, l + r + 1)
            return max(l, r) + 1
        depth(root)
        return self.index - 1

0 赞同 0 条回复

mpweixin用户永久会员 2022年11月4日下午8:02

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

时间空间复杂度O（n)
递归，我觉得一定要从宏观语境去把握递归！！！

0 赞同 0 条回复

y 普通 2022年11月4日下午6:25

// 左节点高度 + 右节点高度 + 1
var diameterOfBinaryTree = function(root) {
  let result = -Infinity;
  const depth = function(root) {
      if(!root) {
          return 0;
      }
      let left = depth(root.left);
      let right = depth(root.right)
    //   更新全局变量
      result = Math.max(result, left + right + 1)
      return Math.max(left,right) + 1;
  }
  depth(root);
  return result - 1;
};

0 赞同 0 条回复

派大星普通 2022年11月4日下午5:11

class Solution {
//计算二叉树的直径就是计算两个任意节点之间的最大长度，用递归的方法自底向上，计算每个节点的左右长度之和取一个最大值
//时间复杂度O(n)
//空间复杂度O(n)
    int sum = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null || (root.left==null && root.right==null)){
            return 0;
        }
        f(root);
        return sum;
    }
    public int f(TreeNode root){
        if(root==null)return 0;
        int leftDiameter = 0;
        int rightDiameter = 0;
        leftDiameter += f(root.left);
        if(root!=null && root.left!=null) leftDiameter++;
        rightDiameter += f(root.right);
        if(root!=null && root.right!=null) rightDiameter++;
        int s = leftDiameter + rightDiameter;
        if(s>sum) {
            sum = s;
        }
        return leftDiameter>rightDiameter ? leftDiameter : rightDiameter;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月4日下午4:44

分析

思路和算树最大高度的那题类似，最大值一定是在二叉树的左右子树高度的和，每次递归将左右子树长度相加与最大值比较并记录，返回左右子树中最大的，时间复杂度为O（n），空间复杂度为O（lgn）.

代码

/**
 * 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 max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        f(root);
        return max;
    }
    int f(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = f(root.left);
        int right = f(root.right);
        max = Math.max(max,left+right);
        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

青木普通 2022年11月4日下午4:30

/**
    比较暴力的方法，前序遍历，将当前节点的左右子树高度加一下，取最大值就好
    缺点是比较慢

    时间复杂度O(n^2)
    空间复杂度O(n)
 */
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        TreeNode p = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        int ans = 0;
        while(p!=null || !stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                ans = Math.max(ans, function(p.left)+function(p.right));
                p = p.left;
            }
            else{
                p = stack.pop();
                p = p.right;
            }
        }
        return ans;
    }

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

/**
    看了题解真是简洁，直接在递归深度的时候就计算直径，不用先计算深度，直接降了下来，我好笨

    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 0;
        function(root);
        return ans;

    }

    public int function(TreeNode root){
        if(root == null) return 0;
        int l = function(root.left);
        int r = function(root.right);
        ans = Math.max(ans, l+r);
        return Math.max(l, r) + 1;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年11月4日下午3:27

递归
时间O(n)
空间O(n)

class Solution {
    int res = 1;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)    return 0;
        f(root);
        return res-1;
    }
    private int f(TreeNode root){
        if(root == null)    return 0;
        int left = f(root.left);
        int right = f(root.right);
        res = Math.max(res,left+right+1);
        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

追普通 2022年11月4日上午11:11

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

先通过深度优先搜索求出左右子树的最大深度，然后得到路径经过的节点数

0 赞同 0 条回复

易水寒永久会员 2022年11月4日上午11:02

树的深度变种，后续遍历

class Solution {
    int max;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }
    private int depth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int L = depth(root.left);//不能在这两层加一
        int R = depth(root.right);
        max = Math.max(max, L+R);
        return Math.max(L, R)+1;//要在这里加一
    }
}

0 赞同 0 条回复

T 普通 2022年11月4日上午7:24

最长路径，等效于路径经过节点最大值 – 1。通过深度优先搜索可求。

class Solution {
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return ans;
        rec(root);
        return ans - 1;
    }

    public int rec(TreeNode node) {
        if(node == null) return 0;
        int L = rec(node.left);
        int R = rec(node.right);
        int num_node = L + R + 1;
        if(num_node > ans) 
            ans = num_node;
        return Math.max(L, R) + 1;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月3日下午9:17

543. 二叉树的直径(11.3)

时间复杂度O(N) 空间复杂度O(N)系统栈最坏情况

/**
易错点：不一定最长路径经过根节点，要以每个节点计算最长路径(左子树边长+右子树)
 */
class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        dfs(root);
        return max;
    }
    public int dfs(TreeNode root){
        if(root.left == null && root.right == null){
            return 0;
        }
        int left = root.left == null ? 0 : dfs(root.left) + 1;
        int right = root.right == null ? 0: dfs(root.right) + 1;
        max = Math.max(left+right,max);
        return Math.max(left,right);
    }
}

雷同题目

124. 二叉树中的最大路径和(11.3)

时间复杂度O(N) 空间复杂度O(N)系统栈最坏情况

相比较于上一题，此处路径要求的是最大和，改变在处理左右子树值的时候，不再是取路径+1，而是直接取左右路径的值加根节点来判断是否为最大

在返回该节点到左右子树中任意一个的最大值

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        dfs(root);
        return max;
    }
    public int dfs(TreeNode root){
        if(root == null) return 0;
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0,dfs(root.right));
        max = Math.max(max,left+right+root.val);//当前路径总和
        return Math.max(left,right) + root.val;
    }
}

687. 最长同值路径(11.3)

时间复杂度O(N) 空间复杂度O(N)系统栈最坏情况

区别在于，因为要判断同值。

最简单的方法就是判断当前节点和左右节点是否相等，相等则保留长度说明同值，不等则为0

class Solution {
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        if(root == null) return 0;
        dfs(root);
        return max;
    }
    public int dfs(TreeNode root){
        if(root == null) return 0;
        int leftSize = root.left != null? dfs(root.left) + 1: 0;
        int rightSize = root.right != null? dfs(root.right) + 1: 0;
        if(leftSize > 0 && root.val != root.left.val){//左子树的长度大于0表示不是null
            //值不同
            leftSize = 0;
        }
        if(rightSize > 0 && root.val != root.right.val){
            rightSize = 0;
        }
        max = Math.max(leftSize + rightSize,max);
        return Math.max(leftSize , rightSize);
    }
}

0 赞同 0 条回复

So 普通 2022年11月3日下午8:17

/**
 * 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 ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) {
            return 0; 
        }
        int L = depth(node.left); 
        int R = depth(node.right); 
        ans = Math.max(ans, L+R+1); 
        return Math.max(L, R) + 1; 
    }
}

时间：O(n)，空间：O(height)

0 赞同 0 条回复

Whatever 永久会员 2022年11月3日下午8:08

分别计算左右子树的最大深度，利用后序遍历的特性，相加得出最大直径。时间O(n)，空间O(n)

class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return res;
    }
    public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        res = Math.max(res,leftMax + rightMax);
        return 1 + Math.max(leftMax,rightMax);
    }
}

0 赞同 0 条回复

【二叉树专题】额外补充：543. 二叉树的直径

共以下 33 个回答

求高度顺便更新一下最大值

分析

代码

543. 二叉树的直径(11.3)

雷同题目

124. 二叉树中的最大路径和(11.3)

687. 最长同值路径(11.3)

# 回答此问题取消回复

【二叉树专题】额外补充：543. 二叉树的直径

共以下 33 个回答

求高度 顺便更新一下最大值

分析

代码

543. 二叉树的直径(11.3)

雷同题目

124. 二叉树中的最大路径和(11.3)

687. 最长同值路径(11.3)

# 回答此问题 取消回复

求高度顺便更新一下最大值

# 回答此问题取消回复