首页 > 代码库 > LeetCode: Balanced Binary Tree 解题报告
LeetCode: Balanced Binary Tree 解题报告
Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Show Tags
SOLUTION 1:
使用inner Class来解决
1 // Solution 1: 2 public boolean isBalanced1(TreeNode root) { 3 return dfs(root).isBalanced; 4 } 5 6 // bug 1: inner class is like: "public class ReturnType {", no () 7 public class ReturnType { 8 boolean isBalanced; 9 int depth;10 11 ReturnType(int depth, boolean isBalanced) {12 this.depth = depth;13 this.isBalanced = isBalanced;14 }15 }16 17 public ReturnType dfs(TreeNode root) {18 ReturnType ret = new ReturnType(0, true);19 20 if (root == null) {21 return ret;22 }23 24 ReturnType left = dfs(root.left);25 ReturnType right = dfs(root.right);26 27 ret.isBalanced = left.isBalanced 28 && right.isBalanced 29 && Math.abs(left.depth - right.depth) <= 1;30 31 // bug 2: remember to add 1( the root depth ) 32 ret.depth = Math.max(left.depth, right.depth) + 1;33 34 return ret;35 }
SOLUTION 2:
将 get depth函数提出
1 // Solution 2: 2 public boolean isBalanced(TreeNode root) { 3 if (root == null) { 4 return true; 5 } 6 7 return isBalanced(root.left) && isBalanced(root.right) 8 && Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1; 9 }10 11 public int getDepth(TreeNode root) {12 if (root == null) {13 return 0;14 }15 16 return Math.max(getDepth(root.left), getDepth(root.right)) + 1;17 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/IsBalanced.java
LeetCode: Balanced Binary Tree 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。