LeetCode 543. Diameter of Binary Tree

原题链接在这里：https://leetcode.com/problems/diameter-of-binary-tree/

题目：

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 longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

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.

题解：

对每一个节点，维护左右的Maximum Depth of Binary Tree相加及时最大直径.

Time Complexity: O(n), n is number of nodes in the tree.

Space: O(logn).

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int diameterOfBinaryTree(TreeNode root) {
12         int [] res = {0};
13         maxDepth(root, res);
14         return res[0];
15     }
16     
17     private int maxDepth(TreeNode root, int [] res){
18         if(root == null){
19             return 0;
20         }
21         
22         int left = maxDepth(root.left, res);
23         int right = maxDepth(root.right, res);
24         res[0] = Math.max(res[0], left+right);
25         
26         return Math.max(left, right)+1;
27     }
28 }

类似Tree Diameter, Longest Univalue Path, Binary Tree Maximum Path Sum.