maxcian der TechBlog

一開始沒有看清楚題目，以為longest path一定會經過root node，原來可以不用

那麼在遞迴含式裡就要考慮每一個node的左子樹與右子樹的最長路徑，是否有大於global longest path，而非直接回傳左邊大或右邊大

根據上述修改後，diameterOfBinaryTree()內也不需要在那邊計算左子樹高+右子樹高，一律丟給compute_height()，然後在每個node中計算它的(左子樹高+右子樹高)是否比global_height還大，最後diameterOfBinaryTree()再回傳global_height即可得解

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        if (!root) return 0;
        compute_height(root);
        return global_height;
        // 以下為以為最長路徑會經過root node時的舊思路
        // int l_deep = compute_height(root->left);
        // int r_deep = compute_height(root->right);
        // return l_deep + r_deep ;
    }
    int compute_height(TreeNode* root)
    {
        if (!root) return 0;
        int l_deep = compute_height(root->left);
        int r_deep = compute_height(root->right);
        global_height= max(global_height, l_deep + r_deep); // 舊思路中沒有此行
        return l_deep >= r_deep ? l_deep+1 : r_deep+1;
    }
    int max(const int& lhs, const int& rhs)
    {
        return lhs >= rhs ? lhs : rhs;
    }
private:
    int global_height= 0;
    
};