题目

解法：后序遍历

思路

通过后序遍历递归计算每个节点的左右子树深度，并在过程中更新全局最大直径（左深度+右深度）。

对于任意节点，经过它的最长路径必然由其左子树的最深路径和右子树的最深路径组成。递归过程确保我们计算每个节点的深度，并在访问每个节点时计算经过该节点的可能最大路径长度。由于维护全局最大值，因此不会遗漏任何候选路径，每个节点的深度仅计算一次，保证了算法的完备性。

• Step 1: 递归终止条件，空节点返回深度0
• Step 2: 递归计算左子树深度L
• Step 3: 递归计算右子树深度R
• Step 4: 更新全局答案ans = max(ans, L + R)
• Step 5: 返回当前子树最大深度max(L, R) + 1

复杂度

• 时间复杂度: $O(n)$，其中 n 是节点数，每个节点仅访问一次。
• 空间复杂度: $O(h)$，其中 h 是树的高度，递归栈空间消耗。

代码

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