首页 > 代码库 > 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.
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 (二叉树的直径)