leetcode 543：二叉树的直径
543. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1 / 2 3 / 4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
**注意：**两结点之间的路径长度是以它们之间边的数目表示。
Related Topics
树
二叉树
思路1：深度优先遍历(递归)
分析:一个节点直径长度有2种方式
- 左右子树的最大直径加1。
- 注意：我们统计左右子树的最大直径加1，但是当左右孩子为null时，需要返回-1，因为-1加1后等于0，叶子节点的直径就是0.
- 当左右孩子是叶子节点的时候，返回0，加1后就等于1.和叶子节点直径距离是1.
- 注意为空和叶子节点的返回值不同。
- 左子树的最大直径加1，再加上 右子树的最大直径加1。
找出整棵树的最大值。
class Solution { public int diameterOfBinaryTree(TreeNode root) { int[] result = dfs(root); return Math.max(result[0],result[1]); } //result[0] 表示当前节点到叶子的最大直径 //result[1]表示这棵树中最大直径 public int[] dfs(TreeNode root){ int[] result = new int[2]; if(root == null){ result[0] = result[1] = -1; return result; } if(root.left ==null && root.right == null){ return result; } int[] left = dfs(root.left); int[] right = dfs(root.right); result[0] = Math.max(left[0],right[0])+1; result[1] = Math.max(left[0]+right[0]+2,Math.max(left[1],right[1])); return result; } }解答成功: 执行耗时:0 ms,击败了100.00% 的Java用户 内存消耗:40.9 MB,击败了41.45% 的Java用户
改进：定义一个全局变量max，函数就不需要当前节点最大值了。
class Solution { private int max = 0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return max; } public int dfs(TreeNode root){ if(root == null){ return -1; } if(root.left ==null && root.right == null){ return 0; } int left = dfs(root.left); int right = dfs(root.right); max = Math.max(left+right+2,max); return Math.max(left,right)+1; } }
