543. Diameter of Binary Tree

這題看似是easy, 我覺得其實蠻有深度的

他在問樹上最大距離的兩點, 這個距離是多少, 另外不用一定要經過root

我卡在這一段時間, 怎麼有找最大值不經過root的

舉例

     1
    / \
   2    3
  / \
 4   5
/     \
6       7
|       \
8         9

可以看到, 上面的case 最大是8 -9, 期間並沒有經過root,

那我們到底在找什麼呢, 我們找左右子數的深度, 但在過程中, 我們會順便檢查這個節點的左右子數深度和, 若這個深度和最大, 他便是這棵樹的圓心

class Solution {
  public:
    int diameterOfBinaryTree(TreeNode *root) {
        int res = 0;
        maxDepth(root, res);
        return res;
    }
    int maxDepth(TreeNode *root, int &res) {
        if (!root)
            return 0;
        int left = maxDepth(root->left, res);
        int right = maxDepth(root->right, res);
        res = max(left + right, res);
        return max(left, right) + 1;
    }
};