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 ofevery node never differ by more than 1.
public class Solution { public boolean isBalanced(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if(root == null) return true; int left = max(root.left); int right = max(root.right); return Math.abs(left - right) <=1 &&isBalanced(root.left)&&isBalanced(root.right);//forget recursion } public int max(TreeNode root){ if (root == null ) return 0; int left_height = max(root.left); int right_height = max(root.right); return (left_height>right_height)?left_height+1:right_height+1; } }
mistake:1) forget recursion for left/right 2) forget use function to calculate tree height
learned: recursion to get true/false in main return function (return first condition && left is ture && right is true)
public class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true; if(root.left == null && root.right == null) return true; int left = max(root.left); int right = max(root.right); return (Math.abs(left - right) <=1) && isBalanced(root.left) && isBalanced(root.right); } public int max(TreeNode node){ if(node == null) return 0; return 1 + Math.max(max(node.left),max(node.right)); } }