解题思路:
1. recursion method, check the height of the left sub tree and right sub tree.
2. Keep track the height of every node, then we iterate the whole tree only one time.
Java Code:
public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; } public int getHeight(TreeNode root){ if(root == null) return 0; int leftheight = 0, rightheight = 0; if(root.left != null) leftheight = getHeight(root.left); if(root.right != null) rightheight = getHeight(root.right); if(leftheight == -1 || rightheight == -1 || Math.abs(leftheight - rightheight) > 1) return -1; int height = leftheight > rightheight? leftheight +1 : rightheight + 1; return height; }
No comments:
Post a Comment