isValidBST
public boolean isValidBST(TreeNode root) {
return valid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean valid(TreeNode root, int low, int high) {
if (root ==null) return true;
return root.val > low && root.val < high
&& valid(root.left.val, low, root.val) && valid(root,right, root.val, high);
}
// Correction:
- the corner case:
if root == null - the first param in "valid" should be TreeNode rather than the value
// isValidBST
public boolean isValidBST(TreeNode root) {
return valid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean valid(TreeNode root, int low, int high) {
if (root ==null) return true;
return root.val > low && root.val < high
&& valid(root.left, low, root.val)
&& valid(root,right, root.val, high);
}
// When the TreeNode contain the infinite, above code won't work;
// so we replace the MAX and MIN with null
private boolean valid(TreeNode root, int low, int high) {
if (root ==null) return true;
return (low == null || root.val > low) && ( high == null || root.val < high)
&& valid(root.left, low, root.val)
&& valid(root,right, root.val, high);
}
// OR we can traverse the Tree using inOrder and check whether the array we obtained is
// monotonically increases.
Balanced binary Tree
// Notice that: by counting the tree balanced or not, we should use the height = MAX depth
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
// if Math.abs(maxDepth(root.left) - maxDepth(root.right) > 1) {return false;}
// return isBalanced(root.left) && isBalanced(root.right);
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
// Above approach recalculates max depth for each node repeatedly,
// we can optimize it by passing the depth bottom up
public boolean isBalanced(TreeNode root) {
return maxDepth(root);
}
public int maxDepth(TreeNode root) {
if (root == null) return 0;
L = maxDepth(root.left);
if (L == -1) return -1;
R = maxDepth(root.rigth);
if (R == -1) return -1;
return (Math.abs(L - R) <= 1) ? (Math.max(L, R) + 1) : -1;
}
网友评论