543. Diameter of Binary Tree

解題思路

一開始的想法是看 root->left 跟 root->right 各自的最大深度，然後加起來就是答案，因為等同於從左邊最深走到右邊最深的路徑。

不過後來有測資錯誤。要考量的不只是 root 底下的左子樹與右子樹，而是所有 node 底下的左子樹與右子樹都要檢查，所以要一直往下 recursive 的 max 當前最大與左右子樹的最大。

程式碼

class Solution {
public:
    int getDepth(TreeNode* p)
    {
        if(p == nullptr)
            return 0;
        return max(getDepth(p->left), getDepth(p->right)) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        if(root == nullptr)
            return 0;
        int left = getDepth(root->left);
        int right = getDepth(root->right);
        int sub = max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right));
        return max(sub, left + right);
    }
};