# LeetCode 543. Diameter of Binary Tree

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

## 題目大意

找出二元樹的直徑
二元樹的直徑定義為樹中兩點之間最長之路徑長

這條路徑並未一定要經過 `root`

## 思考

<img src="https://media.geeksforgeeks.org/wp-content/uploads/Diameter-of-Binary-Tree.png" style="display:block;margin:auto;width:70%;height:auto;">

[[ref]](https://www.geeksforgeeks.org/diameter-of-a-binary-tree/)

上面這張圖說明了二元樹之直徑不一定需要經過 `root`

那麼這題該如何思考呢？
其實我們就對每個點看其左右子樹高，只要當前出現了比較長的路徑，就把答案更新
如此一來就可以交卷了

class Solution
{
public:
    int diameterOfBinaryTree(TreeNode *root)
    {
        int ans = 0;
        helper(root, ans);

        return ans;
    }

private:
    int helper(TreeNode *node, int &ans)
    {
        if (!node)
            return 0;

        int left = helper(node->left, ans);
        int right = helper(node->right, ans);
        ans = max(ans, left + right);

        return max(left, right) + 1;
    }
};