[LeetCode] 543. Diameter of Binary Tree

轉自LeetCode

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longestpath between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree 

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

<Solution>

想法如下

• 歷遍整個樹，把每個 node 都當做 root，那麼以此 node 為 root 的最長 path 就會是 左子樹深度 + 右子樹深度

• 過程中，記錄最長的 path，最後就是答案

code如下

C++