題目： LeetCode - 543. Diameter of Binary Tree

題目說明

給一個 Tree，找出它的最長路徑。

解題思路

核心想法為，最長路徑有沒有通過 root？

  • 若有：最長路徑為 左邊 node 的最深深度 加上 右邊 node 的最深深度。

  • 若沒有：最長路徑為 左邊 node 的最長路徑 或是 右邊 node 的最長路徑。

確定了上面想法後再利用遞迴的觀念找出答案即可。
Tree 的最深深度的算法可參考：LeetCode - 104 解題紀錄

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    
    int maxDepth(TreeNode* root)
    {
        if(!root)
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
    
    int diameterOfBinaryTree(TreeNode* root) {
        // 終止條件
        if(!root) 
            return 0;
        // 包含 root 的最長路徑
        int middle = maxDepth(root->left) + maxDepth(root->right);
        // 只有右邊的最長路徑
        int right = diameterOfBinaryTree(root->right);
        // 只有左邊的最長路徑
        int left = diameterOfBinaryTree(root->left);
        
        return max(middle, max(right, left));
    }
};