首页 > 代码库 > LeetCode 543. Diameter of Binary Tree (二叉树的直径)

LeetCode 543. 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 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.

 


 题目标签:Tree
  这道题目给了我们一个二叉树,让我们找到二叉树的直径 - 最远的距离存在于两个点之间。 我们另外需要一个function - getDepth。 这个function利用post order,从最左边下面开始返回每一个点的depth, 如果这个点是null,那么返回0,依次像上一个level,每次加1。
在知道了每一个点的depth之后,我们可以来找到树的最大直径。我们来分析一下,怎么找到最大直径,取题目中给的例子,我们只看2 4 5 这基本结构, 2 4 5 这个子树的最大直径是2,这个直径等于 2的left 4的depth(1) 和 2的right 5的depth(1),两边的depth之和就等于最大直径 。 我们再回到原来的树立,1,2,3,4,5这个原题中的例子,我们从下往上看, 4的depth = 1, 5的depth = 1, 对于每一个parent node 取两个children的depth之和,和之前的diameter比较,大的就取代。 所以2的diameter = 2; 接着看2的depth = 2, 3的depth = 1, 那么1的diameter = 2 + 1  = 3, 比之前的diameter大,所以最大直径等于3。
 
对于每一个点,left 和 right depth 之和,就等于这个点的最大直径。换一句话说,就是这个点,左边能延伸出去最大值 + 右边能延伸出去的最大值,加一起,就等于这个点的左边最远的点到右边最远的点的距离。 就是最大直径。
 
 

Java Solution:

Runtime beats 72.26% 

完成日期:06/30/2017

关键词:Tree

关键点:用post order去返回每一个点的depth(在之前depth值上+1),null点就返回0(base case);

    需要两个function,因为getDepth function 返回的都是depth,不是diameter,所以需要diameterOfBinaryTree 来单独返回diameter;

    每一个点的最大直径等于左边的depth 加上 右边的depth,取所有点中最大的值。

 

 

 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 {
12     int diameter = 0;
13     
14     public int diameterOfBinaryTree(TreeNode root) 
15     {
16         getDepth(root);
17         
18         return diameter;
19     }
20     
21     public int getDepth(TreeNode root)
22     {
23         if(root == null)
24             return 0;
25         
26         int left = getDepth(root.left);
27         int right = getDepth(root.right);
28         
29         int temp = left + right;
30         
31         if(temp > diameter)
32             diameter = temp;
33         
34         return Math.max(left, right) + 1;
35     }
36 }

参考资料:

http://blog.csdn.net/zhouziyu2011/article/details/64123326

改动了一下,因为temp = left + right + 2 有点绕。返回0更直接易懂。

 
 

LeetCode 543. Diameter of Binary Tree (二叉树的直径)