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

小肸永久会员 2023年9月3日下午3:44

class Solution {
    static int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        res = 0;
        dfs(root);
        return res;
    }
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftDepth = dfs(node.left);
        int rightDepth = dfs(node.right);
        //对于一个节点而言的最长路径，就是它的左子树的最大深度+右子树的最大深度
        res = Math.max(leftDepth + rightDepth, res);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月31日上午11:54

递归思想很重要。。。

/**
 * 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 + 1); // 每到一点都更新当前最大值
        return max(L, R) + 1; // 返回单前节点为根的子树深度
    }
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans-1;
    }
};

0 赞同 0 条回复

sincere 普通 2023年8月29日下午9:48

思路：获取每个子节点的深度，最大长度就是左右深度之和
复杂度：时间复杂度O(n)，空间复杂度O(log2n)

class Solution {
    private int ans = 0;

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

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

0 赞同 0 条回复

c 普通 2023年8月25日下午9:53

深度优先遍历，通过左右孩子节点的深度来判断当前节点作为根节点的最大长度

class Solution {
    int max=0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max-1;
    }
    public 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+1);
        return 1+Math.max(L,R);
    }
}

0 赞同 0 条回复

帝心引力永久会员 2023年8月25日下午8:37

时间o(n), 空间o(n)
class Solution {
public:
    int ans;
    int depth(TreeNode* root){
        if(root == NULL) return 0;
        int ldepth = depth(root->left);
        int rdepth = depth(root->right);
        ans = max(ans, ldepth+rdepth+1);
        return max(ldepth, rdepth) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

0 赞同 0 条回复

别扒拉我普通 2023年8月24日下午9:24

深度优先遍历

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

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

0 赞同 0 条回复

行动派小彩笔普通 2023年8月24日下午6:27

 
 // 计算二叉树深度的思想，计算过程中，记录最高的直径
// 时间复杂度O(n),空间复杂度O(log n);
class Solution {
public:
    int height = 0;
    int depth(TreeNode* root)
    {
        if(!root) return 0;
        int left = depth(root->left);
        int right = depth(root->right);
        height = std::max(height,left+right);
        return std::max(left,right)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        depth(root);
        return height;
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月24日下午3:21

二叉树直径：左右子树最大深度的和；
遍历所有节点过程中得到所有节点的直径，更新最大直径
O(n)

class Solution {
public:
    int max { 0 };
    int dfs(TreeNode* node) {
        if (node == nullptr)  {
            return 0;
        }

        int left = dfs(node->left);
        int right = dfs(node->right);

        max = std::max(max, left + right);
        return std::max(left, right) + 1;

    }

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

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月24日下午2:52

左右子树深度加和最大的即为二叉树的直径

class Solution {
    int ans;

    public int diameterOfBinaryTree(TreeNode root) {
        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;
    }
}

1 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复