# Leetcode [No. 543] Diameter of Binary Tree(EASY)

+ 2024/02/27 Daily Challenge

## 題目

https://leetcode.com/problems/diameter-of-binary-tree/description/

## 思路
首先我覺得這題應該要是medium ==
+ 一開始看題目的testcase會認為說，只要找到左邊的最深度，跟右邊的最深度再加起來就好。
+ 但是實際submit的時候會遇到一個很討厭的測資：
+ 
+ 這個測資告訴我們，最遠的不一定會經過root，所以在做計算的時候不能只做一次recursive，而是要考慮每一個node的diameter，所以要取node本身(left+right)， node->left and node->right.

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(root == nullptr) return 0;
        int left_depth = findNodeDepth(root->left);
        int right_depth = findNodeDepth(root->right);
        return std::max({left_depth+right_depth, diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)});
    }

    int findNodeDepth(TreeNode* node)
    {
        if(node == nullptr) 
        {
            return 0;
        }
        if(node->left == node->right)
        {
            return 1;
        }
        int left_depth = findNodeDepth(node->left);
        int right_depth = findNodeDepth(node->right);
        return max(left_depth, right_depth) + 1;
    }
};

### 解法分析
+ time complexity: O(nlgn)

### 執行結果

---

## 改良（二刷）

+ 2025/04/27 在刷neetcode150的時候突然看到一個瞬間好懂的解釋：只要找到每一個點的最深就好，重點是每次訪問node時都要更新最大直徑。

https://ithelp.ithome.com.tw/articles/10227129

class Solution {
public:
    int maxDiameter = 0; 
    int diameterOfBinaryTree(TreeNode* root) {
        maxTreeDepth(root);
        return maxDiameter;
    }
    int maxTreeDepth(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        } 
        int leftDepth = maxTreeDepth(node->left);
        int rightDepth = maxTreeDepth(node->right);
        // update maxDiameter when visit node every time.
        maxDiameter = max(maxDiameter, leftDepth + rightDepth);
        return max(leftDepth, rightDepth)+1;
    }
};

## 執行結果