九号球普通 2023年11月19日下午10:11

“`java
求每个节点的直径，找出最大值
class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 0;
depth(root);
return ans;
}

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);
    return Math.max(L, R) + 1;
}

}

0 赞同 0 条回复

招舟子普通 2023年8月26日下午8:43

class Solution {
int max;
public int diameterOfBinaryTree(TreeNode root) {
max=0;
int a =depth(root);
return max;
}
int depth(TreeNode root){
if(rootnull){
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 条回复

jhfuture 普通 2023年8月16日下午9:41

“`java
时间复杂度为O（n）空间为O（n.depth）
class Solution {
int max=0;
public int diameterOfBinaryTree(TreeNode root) {
if(root==null) return 0;
// 最长的一定是两个结点之间
//使用深度优先算法请求每个结点的深度，然后使用一个max变量进行保存

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

    if(L+R>max){
        max=L+R;
    }
    return Math.max(L,R)+1;

}

}

0 赞同 0 条回复

CV大神普通 2023年7月21日上午8:18

class Solution {
    /**
     * 记录深度
     */
    private int maxD = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return maxD;

    }

    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //注意，这里层级深度是，子深度+本层深度（1）
        int leftSize = root.left == null ? 0 : dfs(root.left) + 1;
        int rightSize = root.right == null ? 0 : dfs(root.right) + 1;
        maxD = Math.max(maxD, leftSize + rightSize);
        return Math.max(leftSize,rightSize);
    }

}

0 赞同 0 条回复

断舍离永久会员 2023年7月14日上午9:11

class Solution {
    //直径长度
    int diameter;

    /*
    * 给你一棵二叉树的根节点，返回该树的直径 。
    * 二叉树的直径是指树中任意两个节点之间最长路径的长度。
    * 这条路径可能经过也可能不经过根节点root。
    * 两节点之间路径的长度 由它们之间边数表示。
    * */
    public int diameterOfBinaryTree(TreeNode root) {
        diameter = 1;
        depth(root);
        return diameter - 1;
    }

    public int depth(TreeNode node) {
        //子树到达叶子结点
        if (node == null) {
            return 0; 
        }
        //左孩子为根的子树的深度
        int left = depth(node.left);
        //右孩子为根的子树的深度
        int right = depth(node.right); 
        //更新数据
        diameter = Math.max(diameter, left+right+1); 
        //返回该节点为根的子树的深度
        return Math.max(left, right) + 1; 
    }

}

0 赞同 0 条回复

彦，，# 普通 2023年7月12日下午9:31

“`cpp
时间复杂度O（n）空间复杂度O（high）
int res;
int depth(TreeNode* node)
{
if(!node) return 0;
int L = depth(node->left);
int R = depth(node->right);
res = max(res, L+R+1);
return max(L,R) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
res = 1;
if(!root) return res-1;
depth(root);
return res-1;

“`cpp

0 赞同 0 条回复

江畅普通 2023年7月12日下午1:28

// 二叉树的直径
// 时间复杂度 O(N)
// 空间复杂度 O(Height)
class Solution {
private:
    int res;

private:
    int depth(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int leftHeight = depth(node->left);
        int rightHeight = depth(node->right);
        res = max(leftHeight + rightHeight, res);
        return max(leftHeight, rightHeight) + 1;
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return res;
    }
};

0 赞同 0 条回复

BOZ 普通 2023年7月12日上午10:56

【思路】对于一条在某个节点处拐弯的path，其最大路径长度即该节点左右子树深度的和
【复杂度】时间复杂度O(n)，空间复杂度O(logn)最差O(n)

class Solution {
    int max_path = 0;
    int _diameterOfBinaryTree(TreeNode *r)  {
        if (!r) return 0;
        int left = _diameterOfBinaryTree(r->left);
        int right = _diameterOfBinaryTree(r->right);
        max_path = std::max(max_path, left + right);
        return std::max(left, right) + 1;
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        _diameterOfBinaryTree(root);
        return max_path;
    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月11日下午3:29

用递归求左右子树的深度，深度和就是当前节点的直径，再用一个全局变量储存每次的直径最大值，最后输出

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

        int left=f(root.left);
        int right=f(root.right);
        ans =Math.max(ans,left+right+1);
        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

Sexypig. 普通 2023年7月10日上午9:38

求二叉树的最大直径，递归的思想。某树的最大直径为其左右子树的最大直径或该节点左右子树的深度之和
时间复杂度遍历了整个二叉树，空间复杂度递归栈也为二叉树大小，都为O(n)

#include <iostream>
using namespace std;

// 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 = 0;
    int diameterOfBinaryTree(TreeNode *root) {
        if (!root) return 0;
        depth(root);
        return res;
    }
    int depth(TreeNode *root) {
        if (!root) return 0;
        int leftDepth = depth(root->left);
        int rightDepth = depth(root->right);
        // 后序遍历位置，该节点最大直径为左右孩子的最大直径或左子树的深度+右子树的深度
        res = max(res, leftDepth + rightDepth);
        return max(leftDepth, rightDepth) + 1;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日上午10:08

class Solution {
    private int max = 1;   //存放最大直径长度

    public int diameterOfBinaryTree(TreeNode root) {
        depthofBinaryTree(root);
        return max - 1;   //注意深度比路径多一个1，所以要减去
    }

    public int depthofBinaryTree(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int left = depthofBinaryTree(root.left);
        int right = depthofBinaryTree(root.right);
        max = Math.max(max, left + right + 1);  //由下至上存放最大值
        return (left > right ? left : right) + 1;
    }
}

时间复杂度是O(N), 遍历了所有节点
空间复杂度是O(height)，对树的高度进行了递归

0 赞同 0 条回复

残月冷骄阳普通 2023年7月6日下午10:23

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(1)$

Code

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

0 赞同 0 条回复

WhyNot 普通 2023年7月6日下午5:04

int max; 

int dfv(struct TreeNode* root){
 if(root==NULL){
        return 0;
    }

    int left=dfv(root->left);
    int right=dfv(root->right);
    max=fmax(left+right,max);

    return fmax(left+1,right+1);
}
int diameterOfBinaryTree(struct TreeNode* root){
    max=0;
    dfv(root);
    return max;
}

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

0 赞同 0 条回复

局外人普通 2023年7月5日下午8:50

思路：因为是二叉是，其最大直径=左子树最大深度+右子树最大深度
时间复杂度： O(n) 空间复杂度：O(n)

class Solution {
    int maxDiameter = 0;
    public int maxDepth(TreeNode root){
        if(root==null)  return 0;

        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);

        maxDiameter = Math.max(maxDiameter, leftMax+rightMax);
        return Math.max(leftMax, rightMax)+1;
    }
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }
}

0 赞同 0 条回复

屠龙手段普通 2023年7月4日下午8:33

同时记录当前节点的直径和子树节点最大直径，时间O(n) 空间O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        left = self.CountSide(root.left)
        right = self.CountSide(root.right)
        return max(left[0] + right[0], max(left[1], right[1]))

    def CountSide(self, root):
        if not root:
            return [0, 0]
        left = self.CountSide(root.left)
        right = self.CountSide(root.right)
        diameter = max(left[0], right[0]) + 1
        return [diameter, max(left[0] + right[0], max(left[1], right[1]))]

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午3:33

深度

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

0 赞同 0 条回复

花老爷普通 2023年7月3日下午4:09

dfs
时间：O(n)
空间：O(n)

class Solution {
    private int ans = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return ans;
    }

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

0 赞同 0 条回复

Dsjh 普通 2023年7月3日下午1:28

MY

c++实现
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        helper(root,diameter);
        return diameter;
    }
    int helper(TreeNode *root, int& diameter){
        if(!root){
            return 0;
        }
        int l = helper(root->left, diameter), r = helper(root->right, diameter);
        diameter = max(l+r, diameter);
        return max(l,r) + 1;
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月3日上午11:12

长度是节点数-1。

int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    public int dfs(TreeNode node){
        if(node == null) return 0;
        int leftPath = dfs(node.left);
        int rightPath = dfs(node.right);
        res = Math.max(res,leftPath + rightPath);
        return Math.max(leftPath,rightPath)+1;
    }

0 赞同 0 条回复

Jerry 普通 2023年7月2日下午8:26

 // 递归
class Solution {
    int maxDiameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    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); //每次递归，计算maxDiameter
        return 1 + Math.max(left, right);
    }
}

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

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月2日下午7:02

做两次递归：1是计算某个节点的最大深度 2是计算某个节点的最大直径（左最大深度+右最大深度）。看了讲解发现可以优化为设置一个全局变量，在获取节点最大深度时，就把左边最大深度+右边最大深度之和与全局变量比较，取最大值。
时间复杂度:O(N^2)
空间复杂度:O(N)

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        // 拆解成子问题：每个节点左子树最长+ 右子树最长，得到最长的
        if(root == null) return 0;
        int d = getMaxDepth(root.left) + getMaxDepth(root.right); // 以root为根节点的最大直径
        int dd = Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)); // 以子节点为根节点的最大直径
        return Math.max(dd, d);

    }

    public int getMaxDepth(TreeNode root){ // 得到节点最长的路径
        if(root == null) return 0;
        return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月2日下午2:10

该结点深度=子节点深度最大值+1
这里假设的叶子结点深度为1

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

0 赞同 0 条回复

张开怀普通 2023年7月2日上午9:09

class Solution{
       int ans;
       int depth(TreeNode* rt){
              if (rt == NULL){
                     return 0;  // 访问到了空间点了，返回为0
              }
              int L = depth(rt->left);  // 左子树的深度
              int R = depth(rt->right);  // 右子树的深度
              ans = max(ans,L+R+1);   // 计算d_node即L+R+1，并更新ans
              return max(L, R)+1;         // 返回该节点为根的子树的深度
       }
public:
       int diameterOfBinaryTree(TreeNode* root){
              ans =1;
              depth(root);
              return ans-1;
       }
}

时间复杂度：O(n)
空间复杂度：O(树的高度)

0 赞同 0 条回复

怀瑾永久会员 2023年7月2日上午12:54

C++实现

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 辅助函数，计算二叉树的直径
int diameterOfBinaryTreeHelper(TreeNode* root, int& diameter) {
    if (root == nullptr) {
        return 0;
    }

    // 递归计算左子树和右子树的最长路径长度
    int leftPath = diameterOfBinaryTreeHelper(root->left, diameter);
    int rightPath = diameterOfBinaryTreeHelper(root->right, diameter);

    // 更新直径
    diameter = max(diameter, leftPath + rightPath);

    // 返回经过该节点的最长路径长度
    return max(leftPath, rightPath) + 1;
}

// 主函数，计算二叉树的直径
int diameterOfBinaryTree(TreeNode* root) {
    int diameter = 0;
    diameterOfBinaryTreeHelper(root, diameter);
    return diameter;
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月2日上午12:32

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        diameter = [0]

        def diameterOfBinaryTreeHelper(root):
            if not root:
                return 0

            leftHeight = diameterOfBinaryTreeHelper(root.left)
            rightHeight = diameterOfBinaryTreeHelper(root.right)

            diameter[0] = max(diameter[0], leftHeight + rightHeight)
            return 1 + max(leftHeight, rightHeight)

        diameterOfBinaryTreeHelper(root)
        return diameter[0]

使用全局变量记录返回高度

0 赞同 0 条回复

yxy 普通 2023年7月2日上午12:21

时间复杂度：O(N)

/**
 * 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 = 0;
    int dfs(TreeNode* root)
    {
        if(!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        res = max(left+right, res);
        return max(left, right)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        dfs(root);
        return res;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月1日下午8:48

//思路：计算左右子树深度后，可以计算经过当前root结点的直径。
//时间O(n) 空间O(h)
class Solution {

    int max = 0;
    //求最大深度的同时，可以求直径
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }

        depth(root);

        return max;
    }

    public int depth(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = depth(root.left);
        int right = depth(root.right);
        //计算每个结点的左右深度后，可以计算直径
        int diameter = left + right;
        max = diameter > max ? diameter : max; //更新最大值

        return left > right ? left + 1 : right + 1;

    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年7月1日下午8:48

//  时间O(n)，空间O(n)
class Solution {
public:
    int ans=0;
    int dfs(TreeNode* root)
    {
        if(!root) return 0;
        int left = dfs(root->left); //右边的节点数
        int right= dfs(root->right); // 左边的节点数
        ans = max(left+right,ans); // 如果root是最后一个节点，ans = left + right;
        return max(left,right)+1; //不是最后一个节点，深度+1
    }
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

0 赞同 0 条回复

伏月三十普通 2023年7月1日下午3:46

时间复杂度：O(n) n是二叉树的节点树
空间复杂度：O(h) h是二叉树的高度

class Solution {
    int ans;
    //返回的是直径长度
    public int diameterOfBinaryTree(TreeNode root) {
        ans=1;
        depth(root);
        return ans-1;
    }

    //给一个递归函数，求的是每一个节点的深度
    int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=depth(root.left);
        int right=depth(root.right);
        ans=Math.max(ans,left+right+1);
        return Math.max(left,right)+1;//求的是每个节点的深度
    }
}

0 赞同 0 条回复

小吕普通 2023年7月1日下午3:37

c++实现
int len;
int depth(TreeNode* root)
{
if(rootNULL)return 0;
int leftdep = depth(root->left);
int rightdep=depth(root->right);
len = max(len,leftdep+rightdep+1);
return max(leftdep,rightdep)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
len = 1;
depth(root);
return len-1;
}

0 赞同 0 条回复

Yodl. 普通 2023年7月1日下午2:28

class Solution {
    int ans;
    int depth(TreeNode* root){
        if (root == NULL) 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;
    }
};
//时间复杂度O(n)
//时间复杂度O(nlogn)

0 赞同 0 条回复

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

共以下 31 个回答

复杂度

Code

MY

# 回答此问题取消回复

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

共以下 31 个回答

复杂度

Code

MY

# 回答此问题 取消回复

# 回答此问题取消回复