1. Same Tree
Given two binary trees, write a function to check if they are equal or not.
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null || q == null)
return p == q;
else
return p.val == q.val && isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right);
}
}
2. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree[1,2,2,3,4,4,3]is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following[1,2,2,null,3,null,3]is not:
1
/ \
2 2
\ \
3 3
public class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root.left);
q.offer(root.right);
while(!q.isEmpty()){
TreeNode left = q.poll();
TreeNode right = q.poll();
if(left==null && right==null) continue;
else if(left==null || right==null) return false;
else if(left.val != right.val) return false;
q.offer(left.left);
q.offer(right.right);
q.offer(left.right);
q.offer(right.left);
}
return true;
}
}
public class Solution {
public boolean isSymmetric(TreeNode root) {
return root==null || isSymmetricHelp(root.left, root.right);
}
public boolean isSymmetricHelp(TreeNode left, TreeNode right) {
if(left==null || right==null)
return left==right;
return left.val==right.val && isSymmetricHelp(left.left, right.right) &&
isSymmetricHelp(left.right, right.left);
}
}
3. Maximum Depth of Binary Tree
public class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
4. Minimum Depth of Binary Tree
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
public class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
int leftTreeHeight = minDepth(root.left);
int rightTreeHeight= minDepth(root.right);
if(leftTreeHeight==0 || rightTreeHeight==0)
return 1 + leftTreeHeight + rightTreeHeight;
else
return 1 + Math.min(leftTreeHeight, rightTreeHeight);
}
}
5. 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 ofeverynode never differ by more than 1.
public class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return check(root) != -1;
}
public int check(TreeNode root) {
if(root == null)
return 0;
int left = check(root.left);
if(left == -1)
return -1;
int right= check(root.right);
if(right == -1)
return -1;
if(Math.abs(left-right) > 1)
return -1;
else
return 1 + Math.max(left, right);
}
}
6. Binary Tree Right Side View
Given a binary tree, imagine yourself standing on therightside of it, return the values of the nodes you can see ordered from top to bottom.
For example: Given the following binary tree,
1
<
---
/ \
2 3
<
---
\ \
5 4
<
---
You should return[1, 3, 4].
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if(root == null) return ans;
rightSideView(root, 0, ans);
return ans;
}
public void rightSideView(TreeNode root, int currDepth, List<Integer> ans) {
if(root == null)
return;
if(currDepth == ans.size())
ans.add(root.val);
rightSideView(root.right, currDepth + 1, ans);
rightSideView(root.left , currDepth + 1, ans);
}
}
7. Invert Binary Tree
1 1
2 3 -> 3 2
public class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
TreeNode left_tree = invertTree(root.left);
TreeNode right_tree= invertTree(root.right);
root.left = right_tree;
root.right= left_tree;
return root;
}
}
public class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
TreeNode node = q.poll();
//swap
TreeNode tmp = node.left;
node.left = node.right;
node.right= tmp;
if(node.left != null) q.offer(node.left);
if(node.right!= null) q.offer(node.right);
}
return root;
}
}
8. Count Complete Tree Nodes
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int d_left = depth(root.left);
int d_right= depth(root.right);
if(d_left == d_right)
return (1 << d_left) + countNodes(root.right);
else
return countNodes(root.left) + (1 << d_right);
}
public int depth(TreeNode root) {
int h = 0;
while(root != null){
root = root.left;
h++;
}
return h;
}
}
9. Lowest Common Ancestor of a Binary Search Tree
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
else if(p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
else if(p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}
10. Lowest Common Ancestor of a Binary Tree
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right= lowestCommonAncestor(root.right, p, q);
return left != null && right != null ? root : right != null? right: left;
}
}
11. Sum of Left Leaves
Find the sum of all left leaves in a given binary tree.
3
/ \
9 20
/ \
15 7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null)
return 0;
if(root.left != null && root.left.left == null && root.left.right == null)
return root.left.val + sumOfLeftLeaves(root.right);
else
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
}