1.Check If Binary Tree Is Balanced
Check if a given binary tree is balanced. A balanced binary tree is one in which the depths of every node’s left and right subtree differ by at most 1.
判断一棵二叉树是否为平衡二叉树，定义:平衡二叉树任意相邻子节点的高度差不能超过1.
Examples
5
/ \
3 8
/ \ \
1 4 11
is balanced binary tree,
5
/
3
/ \
1 4
is not balanced binary tree.
Corner Cases
What if the binary tree is null? Return true in this case.
Solution1：
效率较低，时空复杂度：space:O(height) height = lgn~n; time:O(n)~O(nlgn)
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int leftH = getHeight(root.left);//O(n/2)
int rightH = getHeight(root.right);//O(n/2)
return Math.abs(leftH-rightH)<=1&&isBalanced(root.left)&&
isBalanced(root.right);
}
private int getHeight(TreeNode root){
if(root == null) return 0;
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
return Math.max(leftH, rightH)+1;
}
Solution2：
时空复杂度：space:O(height) height=lgn~n; time:O(n)
public class Solution {
public boolean isBalanced(TreeNode root) {
int height = getHeightIfBlanced(root);
return height!=-1;
}
private int getHeightIfBlanced(TreeNode root){
if(root==null) return 0;
int unBalanced = -1;
int leftH = getHeightIfBlanced(root.left);
if(leftH == unBalanced)return unBalanced;
int rightH = getHeightIfBlanced(root.right);
if(rightH == unBalanced)return unBalanced;
if(Math.abs(leftH-rightH)>1){
return unBalanced;
}
return Math.max(leftH, rightH)+1;
}
}
}
2.Check if a given binary tree is symmetric.
Check if a given binary tree is symmetric.
Examples
5
/ \
3 3
/ \ / \
1 4 4 1
is symmetric.
5
/ \
3 3
/ \ / \
1 4 1 4
is not symmetric.
Corner Cases
What if the binary tree is null? Return true in this case.
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null)return true;
return isSymmetric(root.left, root.right);
}
//time complexity:O(n) space complexity:O(height) height=lgn~n
private boolean isSymmetric(TreeNode node1, TreeNode node2){
if(node1 == null && node2 == null)return true;
if(node1 == null || node2 == null)return false;
//pre-order
if(node1.key != node2.key)return false;
return isSymmetric(node1.left, node2.right)&&isSymmetric(node1.right, node2.left);
}
}
2.Tweaked Identical Binary Trees
Determine whether two given binary trees are identical assuming any number of ‘tweak’s are allowed. A tweak is defined as a swap of the children of one node in the tree.
Examples
5
/ \
3 8
/ \
1 4
and
5
/ \
8 3
/ \
1 4
the two binary trees are tweaked identical.
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
public class Solution {
//time complexity:O(n^2); space complexity:O(height)
public boolean isTweakedIdentical(TreeNode one, TreeNode two) {
if(one == null && two == null)return true;
if(one == null || two == null)return false;
if(one.key!=two.key)return false;
return isTweakedIdentical(one.left, two.left)&&isTweakedIdentical(one.right, two.right)
||isTweakedIdentical(one.left, two.right)&&isTweakedIdentical(one.right, two.left);
}
}
3.Determine if a given binary tree is binary search tree.
Assumptions
There are no duplicate keys in binary search tree.
You can assume the keys stored in the binary search tree can not be Integer.MIN_VALUE or Integer.MAX_VALUE.
Corner Cases
What if the binary tree is null? Return true in this case.
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
//Solution1
public class Solution {
//time complexity:O(n^2)
//space complexity:O(height)
public boolean isBST(TreeNode root) {
if(root==null)return true;
int leftMax = getMax(root.left);
int rightMin = getMin(root.right);
if(leftMax>=root.key || rightMin<=root.key)return false;//root is BST
return isBST(root.left)&&isBST(root.right);//left subtree and right subtree are BST
}
private int getMax(TreeNode root){
if(root==null)return Integer.MIN_VALUE;
int max1 = getMax(root.left);
int max2 = getMax(root.right);
int max3 = Math.max(max1, max2);
return Math.max(max3, root.key);
}
private int getMin(TreeNode root){
if(root==null)return Integer.MAX_VALUE;
int min1 = getMin(root.left);
int min2 = getMin(root.right);
int min3 = Math.min(min1, min2);
return Math.min(min3, root.key);
}
}
//Solution2
//time complexity:O(n)
//space complexity:O(height)
public boolean isBST(TreeNode root) {
if(root==null)return true;
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBST(TreeNode root, int min, int max){
if(root == null)return true;
if(min>=root.key||max<=root.key)return false;
return isBST(root.left, min, root.key)&&
isBST(root.right, root.key, max);
}
//Solution3
//time complexity:O(n)
//space complexity:O(height)
int lastSeen = Integer.MIN_VALUE;
public boolean isBST(TreeNode root){
lastSeen = Integer.MIN_VALUE;
return inOrder(root);
}
private boolean inOrder(TreeNode root){
if(root == null) return true;
if(!inOrder(root.left))return false;
if(lastSeen>=root.key)return false;
lastSeen = root.key;
return inOrder(root.right);
}
4.Get Keys In Binary Search Tree In Given Range
Get the list of keys in a given binary search tree in a given range[min, max] in ascending order, both min and max are inclusive.
Examples
5
/ \
3 8
/ \ \
1 4 11
get the keys in [2, 5] in ascending order, result is [3, 4, 5]
Corner Cases
What if there are no keys in the given range? Return an empty list in this case.
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
public class Solution {
//time:O(lgn) space:O(height)
public List<Integer> getRange(TreeNode root, int min, int max) {
List<Integer> list = new ArrayList<>();
inOrder(root, min, max, list);
return list;
}
private void inOrder(TreeNode root, int min, int max, List<Integer> list){
if(root==null)return;
if(min<root.key)inOrder(root.left, min, max, list);//branch pruning
if(min<=root.key&&max>=root.key)list.add(root.key);
if(max>root.key)inOrder(root.right, min, max, list);
}
}
