leetcode|leetcode 543(二叉树的直径)

leetcode 543:二叉树的直径 543. 二叉树的直径 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树

1 / \ 23 / \ 45

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
**注意:**两结点之间的路径长度是以它们之间边的数目表示。
【leetcode|leetcode 543(二叉树的直径)】Related Topics

深度优先搜索
二叉树
思路1:深度优先遍历(递归) 分析:一个节点直径长度有2种方式
  1. 左右子树的最大直径加1。
    1. 注意:我们统计左右子树的最大直径加1,但是当左右孩子为null时,需要返回-1,因为-1加1后等于0,叶子节点的直径就是0.
    2. 当左右孩子是叶子节点的时候,返回0,加1后就等于1.和叶子节点直径距离是1.
    3. 注意为空和叶子节点的返回值不同。
  2. 左子树的最大直径加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; } }

    推荐阅读