題目網址：https://leetcode.cn/problems/diameter-of-binary-tree/

題意：給一 BT, 求任兩點的 path 之最大長度。

  • 最大長度：最長 path 上的 edge 數

Solution：

想法：利用 DFS, LP(node) 返回以 node 為 root 的 subtree 之最長路徑, 只有當前 node 可以同時使用左子樹和右子樹（由左至右分別是 1, 2, 1）, 也就是計算 res 時可用, 但返回時只能 return 單邊路徑。由於 path 不一定要經過 root, 因此可用 global 變數 res 來記錄最長 path 之長度

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        res = 0;
        LP(root);
        return res;
    }

private:
    int res;

    int LP(TreeNode* root){
        if (!root) {
            return -1;
        }

        const int left = LP(root->left) + 1;
        const int right = LP(root->right) + 1;
        res = max(res, left + right); // 只有當前 root 可以同時使用左子樹和右子樹

        return max(left, right); // 每個 node 都看成是轉折點, 只能返回單邊路徑
    }
};
  • time：$O(n)$ ➔ 遍歷整個 BT
  • space：$O(n)$ ➔ 取決於遞迴深度, worse case：skew tree