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

NULL 普通 2024年3月21日下午2:15

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

0 赞同 0 条回复

紫芝普通 2024年3月18日下午1:44

思路：递归计算路径：maxDepth()函数返回根节点root的左子树和右子树的高度，最长路径为 max(left+right, maxlength)

“`c++
class Solution {
public:
int maxlength;
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
if (maxlength < left+right) { maxlength = left+right; } return 1 + max(left, right); } int diameterOfBinaryTree(TreeNode* root) { maxlength = 0; maxDepth(root); return maxlength; } }; ```

0 赞同 0 条回复

mpweixin用户普通 2024年3月15日下午9:39

java
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;
}

}
提交

0 赞同 0 条回复

言之命至普通 2024年3月15日下午8:23

两个节点之间的最短路径为共同父节点的左右节点最大深度之和+1

int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 0;//局部变量
        depth(root);
        return ans ;
    }
    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); // 计算d_node即L+R 并更新ans
        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
    }

时间复杂度：O（N）

空间复杂度：树的深度。

0 赞同 0 条回复

Raphtalia. 普通 2024年3月15日下午2:08

/**
* 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 maxLength = 0;
int diameterOfBinaryTree(TreeNode root) {
//二叉树的直径 = 左子树 + 右子树的链长 + 2
dfs(root);
return maxLength – 1;
}
int dfs(TreeNode* root){
if(root nullptr) return 0;
int l = dfs(root->left);
int r = dfs(root->right);
maxLength = max(maxLength, l + r + 1);
return 1 + max(l, r);
}
};
时间复杂度O(N),空间复杂度O（n）

0 赞同 0 条回复

kfaebot 普通 2024年3月15日上午10:39

/**
 * 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:
    //步骤1：定义返回值和参数
    int answer=0;
    int nodelength(TreeNode* node){
        //步骤2：定义终止条件
        if(node==nullptr){
            return 0;
        }
        //步骤3：定义遍历过程
        int leftlength=nodelength(node->left);
        int rightlength=nodelength(node->right);
        int lengthsum=leftlength+rightlength+1;

        answer=max(answer,lengthsum);
        return max(leftlength,rightlength)+1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        nodelength(root);
        return answer-1;
    }
};
//时间复杂度和空间复杂度为O(N)

0 赞同 0 条回复

神经蛙普通 2024年3月14日下午11:56

class Solution {
int ans;
int depth(TreeNode* rt){
if (rt NULL) {
return 0;
}
int L = depth(rt->left);
int R = depth(rt->right);
ans = max(ans, L + R + 1);
return max(L, R) + 1;
}
public:
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans – 1;
}
};
思路：二叉树的直径等于所有节点的中某个节点的左右节点个数之后的最大值减去-1

0 赞同 0 条回复

Jimmy 普通 2024年3月14日下午9:44

两个节点之间的最短路径为共同父节点的左右节点最大深度+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;
    int depth(TreeNode *root){
        if(root == nullptr){
            return 0;
        }
        int L = depth(root->left);
        int R = depth(root->right);
        ans = max(ans,L+R);//贪心
        return max(L,R) + 1;//两个节点之间的最短路径为共同父节点的左右节点深度之和+1
    }

    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return ans;
    }
};

0 赞同 0 条回复

王位詮釋普通 2024年3月14日下午3:09

···java
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return max;
}
public int depth(TreeNode root){
if(rootnull){
return 0;
}
int left = depth(root.left)+1;
int right = depth(root.right)+1;
max = max>(left+right-2)?max:(left+right-2);
return left>right?left:right;
}
}
思路：设置一个代表距离的量，深度遍历完之后获取准确的值，然后返回。
由题可知二叉树的直径肯定是两个叶子节点之间的距离，所以就计算以每一个节点为根，算其左右子树的深度，深度之和减去2（两棵子树都多算了根节点自身的深度），然后每次计算完之后与保存的max进行对比，如果max大就不变，否则就更新max值
遍历了每个节点，时间复杂度O(n)
···

0 赞同 0 条回复

云无深雁影普通 2024年3月14日下午2:38

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

}
//时间复杂度On
//空间复杂度On
//使用递归

0 赞同 0 条回复

Yuki 永久会员 2024年3月14日上午10:56

老实说，没完全明白
class Solution {
private:
int res;

//以root为根节点的二叉树深度
int depth(TreeNode*root){
    if(root==nullptr)return 0;

    int ldepth=depth(root->left);//左子树深度
    int rdepth=depth(root->right);//右子树深度

    //一边遍历一边计算以每个节点为根的最长直径
    res=max(ldepth+rdepth+1,res);

    return max(ldepth,rdepth)+1;//每次递归深度加一

}

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

0 赞同 0 条回复

方铎码农普通 2024年3月14日上午9:46

// 深度优先遍历
class Solution {
    int ans;

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

    private 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 条回复

Thaddeus 永久会员 2024年3月14日上午8:49

打卡

/*
注意！：最大直径是任两个节点之间的，也就是说，最长的路径不一定是出现在以根为分界的一个左右路径中。
        而是可能出现在根的某一个子树中，以他为分界的左右子树组成的一个完整的最长路径
因此：在递归的时候，需要用一个值来保存每次比较更新的最大直径值
*/
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxPath(root);
        return res - 1;
    }
private:
    int res = 0;
    int maxPath(TreeNode* root) {
        if(!root) return 0;
        int leftPath = maxPath(root->left);
        int rightPath = maxPath(root->right);
        res = max(res, 1 + leftPath + rightPath);
        return 1 + max(leftPath, rightPath);
    }
};

0 赞同 0 条回复

Yox 普通 2024年3月14日上午1:58

class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 1
def depth(node):
# 访问到空节点了，返回0
if not node:
return 0
# 左儿子为根的子树的深度
L = depth(node.left)
# 右儿子为根的子树的深度
R = depth(node.right)
# 计算d_node即L+R+1 并更新ans
self.ans = max(self.ans, L + R + 1)
# 返回该节点为根的子树的深度
return max(L, R) + 1

    depth(root)
    return self.ans - 1

时间 o n 空间 o height

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月13日下午11:31

class Solution {
    int ans=0;
    public 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 1 + Math.max(left, right);
    }

    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null || ( root.right==null && root.left==null)) return 0;

        maxDepth(root);
        return ans;
    }

}

0 赞同 0 条回复

heathhou 普通 2024年3月13日下午10:00

class Solution {
public:
    int ans = 1; // 半径经过的节点数

    int diameterOfBinaryTree(TreeNode* root) {

        deepTree(root);
        return ans - 1;
    }

    // 递归函数：求二叉树的高度
    int deepTree(TreeNode* root){
        if(root == nullptr){
            return 0;
        }else if(root->left == nullptr && root->right == nullptr){
            return 1;
        }

        int l = deepTree(root->left);
        int r = deepTree(root->right);

        // 更新ans
        ans = max(ans, l + r + 1);

        return max(l, r) + 1;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月13日下午9:20

public int diameterOfBinaryTree(TreeNode root) {
if(root null) return 0;
return depth(root.left)+depth(root.right);
}
int depth(TreeNode root){
if(rootnull) return 0;
return (depth(root.left)>depth(root.right)? depth(root.left):depth(root.right))+1;
}
思路：直径等于左右深度相加

0 赞同 0 条回复

MARS 普通 2024年3月13日下午8:41

day12第一题

var diameterOfBinaryTree = function (root) {
    let ans = 0
    const dfs = (root) => {
        if (root == null) return 0
        let left = dfs(root.left)
        let right = dfs(root.right)
        ans = Math.max(left + right, ans)  //二叉树的直径就是一个节点的左右节点深度
        return Math.max(left, right) + 1
    }
    dfs(root)
    return ans
};

0 赞同 0 条回复

机电皮怪永久会员 2024年3月13日下午8:37

深度优先搜索然后计算左子树+右子树的最大深度
时间复杂度O(n)
空间复杂度O(1)

“`C++
class Solution {
private:
int max;
//DFS
int DFS(TreeNode* root)
{
//递归结束条件
if(root == nullptr)
{
return 0;
}
//最深左子树+最深右子树为节点直径
int deep_left = DFS(root->left) ;
int deep_right = DFS(root->right);
if(deep_left + deep_right + 1 > max)
{
max = deep_left + deep_right;
}
return std::max(deep_left, deep_right) + 1;
}

public:
int diameterOfBinaryTree(TreeNode* root)
{
this->max = 0;
DFS(root);
return max;
}
};

“`

0 赞同 0 条回复

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

共以下 19 个回答

# 回答此问题取消回复

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

共以下 19 个回答

# 回答此问题 取消回复

# 回答此问题取消回复