Maximum Depth of Binary Tree

★☆☆☆☆

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftD = maxDepth(root.left);
        int rightD = maxDepth(root.right);
        return Math.max(leftD, rightD) + 1;
    }
}

Minimum Depth of Binary Tree

★★☆☆☆

Given a binary tree, find its minimum depth. 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 leftD = minDepth(root.left);
        int rightD = minDepth(root.right);
        return (leftD == 0 || rightD == 0)? leftD + rightD + 1: Math.min(leftD, rightD) + 1;
    }
}

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 of every node never differ by more than 1.

public class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root) != -1;
    }
    public int helper(TreeNode node) {
        if (node == null) return 0;
        int lDepth = helper(node.left);
        if (lDepth < 0) return -1;
        int rDepth = helper(node.right);
        if (rDepth < 0) return -1;
        return (Math.abs(lDepth - rDepth) > 1)? -1: Math.max(lDepth, rDepth) + 1;
    }
}

Same Tree

★☆☆☆☆

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null)
            return p == q;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Symmetric Tree

★★☆☆☆

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return helper(root.left, root.right);
    }
    public boolean helper(TreeNode left, TreeNode right) {
        if (left == null || right == null)
            return left == right;
        if (left.val != right.val)
            return false;
        return helper(left.left, right.right) && helper(left.right, right.left);
    }
}

Invert Binary Tree

★★☆☆☆

     4
   /   \
  2     7
 / \   / \
1   3 6   9
==>
     4
   /   \
  7     2
 / \   / \
9   6 3   1

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode tmp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(tmp);
        return root;
    }
}