【二叉树专题】543. 二叉树的直径-跟着帅地玩副业，开拓第二曲线PlayOffer

ppopp 普通 2023年8月27日下午12:38

/**
* 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 {
private:
int res;
public:
int diameterOfBinaryTree(TreeNode root) {
conth(root);
return res – 1;
}

int conth(TreeNode* root){
    if(!root) return 0;
    int left = conth(root->left);  //返回值为包括了左子树的深度
    int right = conth(root->right);
    res = max(res, left+right+1); //边数
    return (left>right? left:right)+1; //结点深度是个数为基准算的
}

};

0 赞同 0 条回复

hi 普通 2023年8月15日上午8:29

递归函数返回的是当前节点的左、右子树的最大值+1

/**
 * 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 ans = 0;

    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* p){
        if(!p) return 0;
        int left = dfs(p->left);
        int right = dfs(p->right);
        ans = max(ans, left + right);
        return max(left, right) + 1;
    }
};

0 赞同 0 条回复

doordie. 普通 2023年8月2日上午10:31

求出左子树和右子树的最大深度之和 = 二叉树的直径

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(ans,L+R+1);
        // 返回该节点为根的子树深度
        return Math.max(L,R)+1;

    }


}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月29日下午3:45

”’java
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
//分别求出左子树的长度和右子树的长度
if(root null){
return 0;
}
int left = height(root.left);
int right = height(root.right);
int rootHeight = left + right;
int leftHeight = diameterOfBinaryTree(root.left);
int rightHeight = diameterOfBinaryTree(root.right);
return Math.max(Math.max(rootHeight,leftHeight),Math.max(rootHeight,rightHeight));
}
//求二叉树的长度
public int height(TreeNode root){
int len = 0;
if(root null){
return 0;
}

    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    return Math.max(leftHeight,rightHeight)+1;
}

}
时间复杂度O(n)
空间复杂度O(1)
”’

0 赞同 0 条回复

北辰普通 2023年7月26日下午5:47

class Solution {
    public int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        //将每一个结点遍历一遍，深度优先搜索
        TreeNode node = root;
        Stack<TreeNode> s = new Stack<>();
        s.add(node);
        while(!s.isEmpty()) {
            TreeNode temp = s.pop();
            ans = Math.max(ans, depth(temp.left)+depth(temp.right)+1);
            if(temp.right!=null) s.add(temp.right);
            if(temp.left!=null) s.add(temp.left);
        }
        return ans-1;
    }

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

思路：对于一棵树，从根节点到它的左子树的最深经过最多结点个数为左子树的树高+1，到右子树同理是右子树的树高+1，那么经过该根节点最多的节点数为左子树高度+右子树高度+1，所以我们可以深度优先遍历该数得到每个结点作为根结点的子树经过该根节点的最多节点数，然后遍历完成后的最大值即为该树的一个结点到另外结点中的最多节点数，然后将该数减一就得到该树的直径。

0 赞同 0 条回复

神经蛙普通 2023年7月25日下午9:07

/**
* 后序遍历处理
*/
class Solution {
    int depth = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return depth;

    }

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

        int leftDpeth = maxDepth(root.left);
        int rightDpeth = maxDepth(root.right);

        depth = Math.max(leftDpeth+rightDpeth, depth);

        return Math.max(leftDpeth, rightDpeth)+1;
    }
}

0 赞同 0 条回复

CKX 普通 2023年7月24日下午1:54

func diameterOfBinaryTree(root *TreeNode) int {
    //递归计算左子树高度、右子树高度，两者之和即直径
    //计算每个节点的直径
    if root == nil {
        return 0
    }
    leftMax := traverse(root.Left)
    rightMax := traverse(root.Right)
    res := leftMax + rightMax
    return max(res, max(diameterOfBinaryTree(root.Left),diameterOfBinaryTree(root.Right)))
}

func traverse(root *TreeNode) int{
    if root == nil {
        return 0
    }
    left := traverse(root.Left)
    right := traverse(root.Right)
    return 1 + max(left, right)
}

func max(a, b int) int{
    if a > b {
        return a
    }
    return b
}

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月23日下午9:57

/**
 * 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 maxd = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        // 转化为根的左右子树的深度之和
        depth(root);
        return maxd;
    }

    public int depth(TreeNode root){
        if(root==null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        // maxd全局只会在根的左右子树更新一次
        // 而不是每层都更新，每层计算的是深度
        maxd = Math.max(maxd, left+right);
        return Math.max(left,right)+1;
    }
}

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

0 赞同 0 条回复

普通 2023年7月23日下午9:53

C++ 代码递归调用
class Solution {
int maxx=0;
public:
int diameterOfBinaryTree(TreeNode* root) {

      if(!root) return 0;
      maxt(root);
      return maxx;
}
int maxt(TreeNode* root)

{
if(!root->left&&!root->right) return 0;
int l=root->leftNULL?0:maxt(root->left)+1;
int r=root->rightNULL?0:maxt(root->right)+1;
maxx= maxx>l+r?maxx:l+r;
return l>r?l:r;
}
};

0 赞同 0 条回复

片言莫语普通 2023年7月23日下午7:09

// 定义Solution类
class Solution {
    // 定义私有变量result并初始化为-1，用于记录最终结果
    private int result = -1;

    // 定义public方法，用于计算二叉树的直径（最长路径）
    public int diameterOfBinaryTree(TreeNode root) {
        // 如果二叉树为空，直径为0
        if (root == null) {
            return 0;
        }
        // 调用depth方法，计算每个节点的深度，并同时更新result
        depth(root);
        // 返回最终结果
        return result;
    }

    // 定义私有方法，用于计算给定节点为根的子树的深度，并更新result
    private int depth(TreeNode root) {
        // 如果节点为空，深度为0
        if (root == null) {
            return 0;
        }
        // 递归计算左子树的深度
        int left = depth(root.left);
        // 递归计算右子树的深度
        int right = depth(root.right);
        // 更新result，取左右子树深度之和的最大值
        result = Math.max(result, left + right);
        // 返回当前子树的深度，即左右子树深度的较大值加1
        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

周小二普通 2023年7月23日下午2:06

//最长路径为左侧的节点数＋右侧的节点数
class Solution {
    private int result = -1;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) {
            return 0;
        }
        depth(root);
        return result ;
    }

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

0 赞同 0 条回复

June 普通 2023年7月21日下午4:04

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 //最长的路径为max(每个结点左右深度之和)，因为两个结点的路径一定要经过他们的某个公共祖先
func diameterOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    var maxLength int = 0
    maxDeep(root,&maxLength)
    return maxLength
}

func maxDeep(root *TreeNode,maxLength *int) int {
    if root == nil {
        return 0
    }
    leftDeep := maxDeep(root.Left,maxLength)
    rightDeep := maxDeep(root.Right,maxLength)
    *maxLength = int(math.Max(float64(leftDeep + rightDeep) , float64(*maxLength)))
    return int(math.Max(float64(leftDeep) , float64(rightDeep) )) + 1
}

0 赞同 0 条回复

人生何处不青山普通 2023年7月21日上午11:41

递归

function diameterOfBinaryTree(root: TreeNode | null): number {
    let max = 0;
    const dfs = (node: TreeNode | null) => {
        if (!node) return 0;
        const left = dfs(node.left);
        const right = dfs(node.right);
        max = Math.max(max, left + right + 1);
        return Math.max(left, right) + 1;
    }
    dfs(root);
    return Math.max(0, max - 1);
};

0 赞同 0 条回复

AD钙奶普通 2023年7月21日上午9:30

左右子树深度之和

class Solution {
    int cnt = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        traversal(root);
        return cnt;
    }

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

0 赞同 0 条回复

#00456B 普通 2023年7月20日下午11:36

思路

就是相当于左右子树的最大深度之和，所以辅助函数就可以直接用一个递归函数来得到每个节点的左右子树的最大高度，得出每个节点的直径。

代码

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

0 赞同 0 条回复

枫梓。普通 2023年7月20日下午2:41

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(1)

0 赞同 0 条回复

mpweixin用户普通 2023年7月20日下午1:01

···java
class Solution {
private int max;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return max;
}
//转换为求二叉树左右子树长度[高度]和的最大值
private int dfs(TreeNode root) {
if(root null){
return 0;
}

    int left = dfs(root.left);
    int right = dfs(root.right);
    // 从当前节点开始计算，不包含当前节点，左子树的最大深度(可以理解成最长的边)加上右子树的最大深度(可以理解成最长的边)
    max = Math.max(left + right, max);
    // 返回当前节点(包含当前节点在内，所以要加1)左右子树的最高深度
    return Math.max(left, right) + 1;

}

}

“`

0 赞同 0 条回复

Marshan 普通 2023年7月20日上午11:00

在二叉树递归的时候, 有时可以通过后序遍历的方式降低时间复杂度

class Solution {
public:
    int maxDiameter = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return maxDiameter;
    }
    // void traverse(TreeNode *root){
    //     if(root == nullptr){
    //         return;
    //     }
    //     int leftMax = maxDepth(root->left);
    //     int rightMax = maxDepth(root->right);

    //     int myDiameter = leftMax + rightMax;

    //     maxDiameter = max(maxDiameter,myDiameter);

    //     traverse(root->left);
    //     traverse(root->right);
    // }
    int maxDepth(TreeNode *root){
        if(root == nullptr){
            return 0;
        }
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);

        int myDiameter = leftMax + rightMax;

        maxDiameter = max(maxDiameter,myDiameter);

        return 1 + max(leftMax,rightMax);
    }

};

0 赞同 0 条回复

V2ero 普通 2023年7月20日上午9:07

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

function diameterOfBinaryTree(root: TreeNode | null): number {
    if(!root) return 0
    let ans = 1;
    const maxHeight = (root: TreeNode | null) => {
        if(!root){
            return 0
        }
        const leftHeight = maxHeight(root.left);
        const rightHieght = maxHeight(root.right);
        ans = Math.max(ans, leftHeight + rightHieght + 1)
        return Math.max(leftHeight,rightHieght) + 1
    }

   maxHeight(root)

    return ans-1
};

0 赞同 0 条回复

艺普通 2023年7月19日下午10:29

“`c++
//时间复杂度:O(n)
//空间复杂度:O(n)
class Solution {
public:
int ans=0;
int dfs(TreeNode* T)
{
if(T==NULL) return 0;
int l=dfs(T->left),r=dfs(T->right);
ans=max(l+r,ans);
return max(l,r)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return ans;
}
};

0 赞同 0 条回复

阿尚普通 2023年7月19日下午9:02

class Solution {
    int maxLen = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        travel(root);
        return maxLen;
    }

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

        int left = travel(root.left);
        int right = travel(root.right);
        maxLen = Math.max(maxLen, left + right);//每个结点的最大直径为  左子树深度 + 右子树深度
        return Math.max(left, right) + 1;//以root节点为根节点的树的深度
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月19日下午8:35

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

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

0 赞同 0 条回复

ONE PIECE 普通 2023年7月19日下午8:25

class Solution {
    int res;
    public int diameterOfBinaryTree(TreeNode root) {
        res = 1;
        depth(root);
        return res-1;
    }

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

时间复杂度：O(n)

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月19日下午7:53

代码

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 left = depth(root.left);
        int right = depth(root.right);
        ans = Math.max(ans, left+right+1);
        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

Mby 普通 2023年7月19日下午6:43

/**
 * 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 max = 0;

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

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

        int left = recursion(root.left);
        int right = recursion(root.right);

        max = Math.max(left + right, max);
        //返回当前节点左右子树的最高深度+1
        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月19日下午4:39

class Solution {
public:
    int BinaryTreePath(TreeNode* root, int& maxPath){
        if(root == nullptr){
            return 0;
        }
        int left = BinaryTreePath(root->left, maxPath);
        int right = BinaryTreePath(root->right, maxPath);
        int sum = left + right;
        maxPath = maxPath > sum? maxPath: sum;
        return max(left,right)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int maxPath = INT_MIN;
        BinaryTreePath(root, maxPath);
        return maxPath;
    }
};

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

0 赞同 0 条回复

NullPointerException 普通 2023年7月19日下午4:20

class Solution {
int max =0;
public int diameterOfBinaryTree(TreeNode root) {
diameterOfBinaryTree1(root);
return max;// 就是路径长度
}
public int diameterOfBinaryTree1(TreeNode root)
{
//最长直径左右两边加起来 max
if(root null)
{
return 0;
}
int left=diameterOfBinaryTree1(root.left);
int right=diameterOfBinaryTree1(root.right);
if((left+right)>max)
{
max=(left+right);
}
return Math.max(left,right)+1;

}
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月19日下午2:29

7.19
Day12：下面是代码

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

0 赞同 0 条回复

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

共以下 28 个回答

思路

代码

# 回答此问题取消回复

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

共以下 28 个回答

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复