Question

link

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a question with standard solution.

It looks like difficult, but actually the code is very short.

Solution

This is my previous solution. Everyone in blogs are having same solution. I mean, every single one of them, one example.

Code

public ArrayList<TreeNode> generateTrees(int n) {
    return construct(0, n);
}

ArrayList<TreeNode> construct(int base, int n) {
    ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
    if (n == 0) ans.add(null);
    for (int cur = 1; cur <= n; cur++) 
        for (TreeNode l : construct(base, cur - 1)) 
            for (TreeNode r : construct(base + cur, n - cur)) {
                TreeNode root = new TreeNode(base + cur);
                root.left = l;
                root.right = r;
                ans.add(root);
            }
    return ans;
}

Question

link

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This seems like an easy recursion question, however it will result in many repeated recursion calls.

To avoid repeated recursion, use Dynamic Programming.

Solution

First code below is my solution. It is a standard recursion solution, but it’s not good. The run time is 30ms more than next code.

Second code is DP solution, where the previous answers are saved and used forfuture calculation. This is the best solution for this question, and I learnt it from this blog.

Code

First code

public int numTrees(int n) {
    if (n <= 1) return 1;

    int total = 0;
    if (n % 2 == 0){
        for (int i = 0; i <= n / 2 - 1; i ++ ){
            // i is all the possible number of nodes on the left
            total += 2 * numTrees(i) * numTrees(n-i-1);
        }
    } else {
        for (int i = 0; i <= (n-1) / 2 - 1; i ++ ){
            // i is all the possible number of nodes on the left
            total += 2 * numTrees(i) * numTrees(n-i-1);
        }
        total += Math.pow(numTrees((n-1)/2), 2);
    }
    return total;
}

Second code

public int numTrees(int n) {
    int[] table = new int[n + 1];
    table[0] = 1;
    table[1] = 1;
    for (int i = 2; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= i; j++) {
            int left = j - 1;
            int right = i - j;
            sum += table[left] * table[right];
        }
        table[i] = sum;
    }
    return table[n];
}

Question

link

    1
   / \
  2   2
 / \ / \
3  4 4  3

    1
   / \
  2   2
   \   \
   3    3

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an easy one.

Solution

I solved it using recursion.

The non-recursion solution is using 2 stacks (or queues). I did not write it, but the code is posted as well, copied from this post.

Code

First, recursion

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return check(root.left, root.right);
}

private boolean check(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    if (left.val != right.val) return false;
    return check(left.left, right.right) & check(left.right, right.left);
}

Second, non-recursion

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    Stack<TreeNode> s1 = new Stack<TreeNode>();
    Stack<TreeNode> s2 = new Stack<TreeNode>();
    s1.push(root.left);
    s2.push(root.right);
    while (!s1.empty() && !s2.empty()) {
        TreeNode n1 = s1.pop();
        TreeNode n2 = s2.pop();
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null) return false;
        if (n1.val != n2.val) return false;
        s1.push(n1.left);
        s2.push(n2.right);
        s1.push(n1.right);
        s2.push(n2.left);
    }
    return true;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very interesting question, with a very tricky solution. Because LinkedList does not have radom access, it is impossible for us to solve it in like we did in last question.

The traditional top-down approach is heavily relied on index operation, and we can’t do that. That is why we solve this question with bottom-up approach. Which is to say, we insert TreeNodes following LinkedList’s order.

I know it’s hard to understand. I found a explanation, but it’s not clear also. The fastest way is to just read the code or write it by hand.

Solution

The key of this solution is a public pointer which traverse thru the list. Each time the pointer procceed, a new TreeNode is added into the final answer. How to keep track of parent TreeNodes? That’s the tricky part. we tree structure is generated before the insertion, altough the values have not been filled in yet.

It’s like doing a DFS in-order traverse thru the tree, and fill in values one by one. In order to know how the tree would look like, prior knowledge of the size of the LinkedList is necessary.

That’s the solution. I’ve never seen a solution like this before, so it’s very important to learn it and memorize it by heart.

Code

standard solution

ListNode cur = null;

public TreeNode sortedListToBST(ListNode head) {
    cur = head;
    int k = 0;
    ListNode temp = head;
    while (temp != null) {
        temp = temp.next;
        k ++;
    }
    return helper(0, k - 1);
}

private TreeNode helper(int left, int right) {
    if (left > right) return null;
    int mid = left + (right - left) / 2;
    TreeNode head = new TreeNode(-1);
    head.left  = helper(left, mid - 1);
    head.val = cur.val;
    cur = cur.next;
    head.right = helper(mid + 1, right);
    return head;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

My first understanding of this question is wrong.

A BST does not necessarily have to fill in left side of the leaf as muc has possible. I was confusing “balanced binary tree” with “left-balanced binary tree”.

A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less

A left-balanced binary tree is a balanced binary tree where the left sub-tree of each node is filled before the right sub-tree

Solution

Then this question become straight-forward.

Code

public TreeNode sortedArrayToBST(int[] num) {
    if (num.length == 0) return null;
    return helper(num, 0, num.length - 1);
}

public TreeNode helper(int[] num, int start, int end) {
    if (start > end) return null;
    int mid = (start + end) / 2;
    TreeNode node = new TreeNode(num[mid]);
    node.left = helper(num, start, mid - 1);
    node.right = helper(num, mid + 1, end);
    return node;
} 

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult question for me.

My first code contains many dulicate calls. I have posted it below as an illustration of bad example.

Solution

The solution should make use of the return value from the recursion, and avoid duplication calls. The standard solution is posted below.

Code

First, my initial solution. It takes 30ms more than next code.

public boolean isBalanced(TreeNode root) {
    // my old code re-submit, for speed test
    if (root == null) return true;
    if (Math.abs(depth(root.left) - depth(root.right)) > 1) {
        return false;
    }
    if (! isBalanced(root.left)) return false;
    if (! isBalanced(root.right)) return false;
    return true;
}

private int depth(TreeNode node) {
    if (node == null) return 0;
    if (node.left == null) return 1 + depth(node.right);
    if (node.right == null) return 1 + depth(node.left);
    return 1 + Math.max(depth(node.left), depth(node.right));
}

Second, the standard solution

public boolean isBalanced(TreeNode root) {
    return helper(root) != -1;
}

private int helper(TreeNode node) {
    if (node == null) return 0;
    int a = helper(node.left);
    if (a == -1) return -1;
    int b = helper(node.right);
    if (b == -1) return -1;
    if (Math.abs(a - b) <= 1) 
        return Math.max(a, b) + 1;
    else return -1;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an easy one

Code

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

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is one of the most difficult questions that I have solved.

The question can be solved using 2 pointers to point to the 2 misplaced nodes, and swap them. I solved the problem with this approach, and I found a good explanation here.

Only two variables (first, second) are enough to record nodes to be exchanged.

If there’s only one descending order pair (e.g. 20, 10, 30, 40, 50), use first & second to record it.

If there are two descending order pairs (e.g. 10, 40, 30, 20, 50 or 50, 20, 30, 40, 10), use the smaller number in second pair to update variable ‘second’.

In the end, swap first and second.

This is a popular solution on the Internet, which uses O(1) space, plus average case O(lgn) stack space (because recursion always incur stack usage). So this solution is actually not fulfilling the requirements.

中序遍历二叉树的空间复杂度是O(logN) on average case

So finally I found a solution with constent space, and it’s using Treaded Binary Tree again! Look below for details.

Solution

This is a systematic analysis of Morris Traversal based on Threaded Binary Tree.

A solution of using Morris Traversal is explained here. Don’t worry about the tree structure being changed, because it’s reverted back after the traversal.

算法2：为了满足O(1)空间复杂度，我们就要使用非递归且不使用栈的中序遍历算法，在leetcode另一个题目Binary Tree Inorder Traversal中，我们提到了Morris Traversal中序遍历算法，它既没有递归，也没有使用栈，而是用了线索二叉树的思想，用闲置的右节点指向中序序列中该节点的后缀，遍历后再恢复树的原始指针。其主要算法步骤如下：

重复以下1、2直到当前节点为空。

Another person have a very good (maybe better) English version of analysis and code:

1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left

Code

First, my code (2 pointer solution)

TreeNode first = null, second = null;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);

public void recoverTree(TreeNode root) {
    helper(root);
    // now first and second are both found
    int temp = first.val;
    first.val = second.val;
    second.val = temp;
}

private void helper(TreeNode root) {
    if (root == null) return;
    helper(root.left);
    if (pre.val > root.val) {
        if (first == null) {
            first = pre;
            second = root;
        }
        else second = root;
    }
    pre = root;
    helper(root.right);
}

Second, real O(1) space solution using Threaded Binary Tree (i.e. Morris Traversal) in C++. I could not memorize this code.

void recoverTree(TreeNode *root) {
       TreeNode *f1=NULL, *f2=NULL;
       TreeNode  *current,*pre, *parent=NULL;

       if(root == NULL)
             return;
       bool found = false;
       current = root;
       while(current != NULL)
       {                
             if(current->left == NULL)
             {
                    if(parent && parent->val > current->val)
                    {
                           if(!found)
                           {
                                 f1 = parent;
                                 found = true;
                           }
                           f2 = current;
                    }
                    parent = current;
                    current = current->right;     
             }   
             else
             {
                    /* Find the inorder predecessor of current */
                    pre = current->left;
                    while(pre->right != NULL && pre->right != current)
                           pre = pre->right;

                    /* Make current as right child of its inorder predecessor */
                    if(pre->right == NULL)
                    {
                           pre->right = current;
                           current = current->left;
                    }

                    /* Revert the changes made in if part to restore the original
                    tree i.e., fix the right child of predecssor */  
                    else
                    {
                           pre->right = NULL;
                           if(parent->val > current->val)
                           {
                                 if(!found)
                                 {
                                        f1 = parent;       
                                        found = true;
                                 }
                                 f2 = current;
                           }
                           parent = current;
                           current = current->right;     
                    } /* End of if condition pre->right == NULL */
             } /* End of if condition current->left == NULL*/
       } /* End of while */

       if(f1 && f2)
             swap(f1->val, f2->val);
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There are various ways to solve this question.

Eg. DFS, BFS, queue and so on.

Solution

I have nothing to say with the code.

Code

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    return helper(root, Integer.MAX_VALUE, 1);
}

private int helper(TreeNode node, int min, int level) {
    if (node == null || level >= min) 
        return min;
    if (node.left == null && node.right == null)
        return level;
    min = helper(node.left, min, level + 1);
    min = helper(node.right, min, level + 1);
    return min;
}

Updated on June 10th, this question is better solved with the Divide & Conquer template! link

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return checkLeaf(root);
}

private int checkLeaf(TreeNode node) {
    if (node == null) {
        return Integer.MAX_VALUE;
    }
    if (node.left == null && node.right == null) {
        return 1;
    }
    int ll = checkLeaf(node.left);
    int rr = checkLeaf(node.right);
    return 1 + Math.min(ll, rr);
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There are various ways to solve this question.

Eg. DFS, BFS, queue and so on.

Solution

I have nothing to say with the code.

Code

public int maxDepth(TreeNode root) {
    return helper(root, 0, 1);
}

private int helper(TreeNode node, int max, int level) {
    if (node == null) return max;
    if (node.left == null && node.right == null)
        return Math.max(max, level);
    max = helper(node.left, max, level + 1);
    max = helper(node.right, max, level + 1);
    return max;
}