543. Diameter of Binary Tree

Loading...LeetCode

在整个树里寻找某个最大数据，还是类似Q968和Q124的思路，dfs遍历同时传递局部解。

968. Binary Tree Cameras124. Binary Tree Maximum Path Sum

• 叶子节点是初始状态，左右子树的最大diameter都是0

• 穿过每个节点的可能最大解，都是左子树diameter+1再加上右子树diameter+1，画图很好理解。

• 所以不停向上传递左右子树分别的diameter即可。

没事儿做还是别拿C++传递数组了，要么用指针搞自己，要么pair累死。

Python

# 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: TreeNode) -> int:
        if not root: return 0
        self.diameter = 0
        self.postorder(root)
        return self.diameter
    
    def postorder(self, root):
        if not root.left and not root.right: return (0, 0)
        l = self.postorder(root.left) if root.left else (-1, -1) 
        leftPath = max(l) + 1
        r = self.postorder(root.right) if root.right else (-1, -1)
        rightPath = max(r) + 1
        self.diameter = max(self.diameter, leftPath+rightPath)
        return (leftPath, rightPath)

C++

/**
 * 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 diameter = -1;
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) {return 0;}
        postorder(root);
        return diameter;
    }

    pair<int, int> postorder(TreeNode* node) {
        pair<int, int> res;
        if (!node) {
            res.first = -1;
            res.second = -1;
            return res;
        }
        pair<int, int> l = postorder(node->left);
        pair<int, int> r = postorder(node->right);
        res.first = max(l.first, l.second) + 1;
        res.second = max(r.first, r.second) + 1;
        diameter = max(diameter, res.first+res.second);
        return res;
    }
};