# 543. Diameter of Binary Tree
###### tags: `LeetCode`
## **Link**
https://leetcode.com/problems/diameter-of-binary-tree
## **題解 1**
題目要求找到一棵二元樹的直徑，即為最長的兩點路徑。

對於一棵不為空的樹，可以拆成左子樹、右子樹和根結點。若最長距離會經過根節點，則最長距離即為左子樹的最大深度+右子樹的最大深度+2。**<font color=#ff0000>一顆空的樹深度為-1</font>**

## **Code 1**

// Wrong Answer
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        return deep(root->left)+deep(root->right)+2;
    }
private:
    int deep(TreeNode* root)
    {
        if(!root)
            return -1;
        return 1+max(deep(root->left),deep(root->right));
    }
};

## **題解 2**
仔細看題目有說最長路徑不一定會經過題目給的root，所以要計算以任意節點為root的情況。於是我們可以很快地寫出：
## **Code 2**

// Accepted
// 時間複雜度 O(n^2)
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        return solve(root);
    }
private:
    int solve(TreeNode* root)
    {
        if(!root)
            return 0;
        return max(deep(root->left)+deep(root->right)+2,max(solve(root->left),solve(root->right)));
    }
    int deep(TreeNode* root)
    {
        if(!root)
            return -1;
        return 1+max(deep(root->left),deep(root->right));
    }
};

## **題解 3**
觀察程式碼之後可以發現我們越下面的路徑會重複算越多次，如果不要重覆計算就可以更快。

因為我們從最初的根往下跑的時候，一定會經過每個節點，所以我們可以在經過每一個節點的時候直接算出當前的最長路徑，並記錄在一個變數中，最後直接回傳變數即可。

變數要當成參數傳進函數或是直接宣在class裡面都可以。
## **Code 3**

// Accepted
// 時間複雜度 O(n)
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        int ans=0;
        deep(root,ans);
        return ans;
    }
private:
    int deep(TreeNode* root, int &ans)
    {
        if(!root)
            return -1;
        int l=deep(root->left,ans),r=deep(root->right,ans);
        ans=max(ans,l+r+2);
        return 1+max(l,r);
    }
};


## date
**2024.02.28**

{%hackmd @nnks8908/background_leetcode %}