543. 二叉树的直径

【题目】：543. 二叉树的直径

class Solution {
public:
    int res = 0;
    // 求节点的最大深度
    int help(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        int l = help(root->left); // 左儿子为根的最大子树深度
        int r = help(root->right); // 右儿子为根的最大子数深度
        res = max(res, l + r); // 更新res
        return max(l, r) + 1; // 返回节点的最大深度
    }

    int diameterOfBinaryTree(TreeNode* root) {
        help(root);
        return res;
    }
};

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

这题要求树的最大直径，其实也就是求树中某一个节点的左右子树的深度之和最大。那么就可以把这个问题拆解成一个个相同子问题：求某一个节点的最大深度。