Daily Archives: July 28, 2016

leetcode 103.

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solution. A naive solution is to use BFS level order traversal. But the code is a bit overhead. However, there is a smart DFS solution. It checks the level. If it adds into result in sequential or reverse order based on level % 2.

This technique can also be used to solve problem like Binary Tree Level Order Traversal II

// DFS solution. Initial root level is 0.
// if level % 2 == 0, sequential order
// if level % 2 == 1, reverse order
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    zigzagHelper(root, ans, 0);
    return ans;
}

private void zigzagHelper(TreeNode root, List<List<Integer>> ans, int level) {
    if (root == null) {
        return;
    }
    if (level >= ans.size()) {
        ans.add(new LinkedList<>());
    }
    LinkedList<Integer> curr = (LinkedList)ans.get(level);
    if (level % 2 == 0) {
        curr.addLast(root.val);
    }
    else {
        curr.addFirst(root.val);
    }
    zigzagHelper(root.left, ans, level + 1);
    zigzagHelper(root.right, ans, level + 1);
}

Check my code on github.

leetcode 105, 106.

Given preorder and inorder traversal of a tree, construct the binary tree.

Given inorder and postorder traversal of a tree, construct the binary tree.

Solution. These two are classical tree problem in data structure class.

For preorder-inorder, the process is like below:

For inorder-postorder, the process is like below:

When we have preorder[preStart], and we want to find inMid. One technique is that we store the inorder[pos] and pos in hashmap. In this way, we can find the inMid in O(1) time.

Preorder-inorder:

public static TreeNode buildTree(int[] preorder, int[] inorder) {
    if (inorder == null) {
        return null;
    }
    HashMap<Integer, Integer> hm = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        hm.put(inorder[i], i);
    }
    return helper(inorder, preorder, 0, inorder.length - 1, 0, preorder.length - 1, hm);
}

private static TreeNode helper(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd, HashMap<Integer, Integer> hm) {
    if (inStart > inEnd) {
        return null;
    }
    int inMid = hm.get(preorder[preStart]);
    TreeNode node = new TreeNode(inorder[inMid]);
    node.left = helper(inorder, preorder, inStart, inMid - 1, preStart + 1, preStart + inMid - inStart, hm);
    node.right = helper(inorder, preorder, inMid + 1, inEnd, preStart + inMid - inStart + 1, preEnd, hm);
    return node;
}

Inorder-postorder:

public static TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder == null) {
        return null;
    }
    HashMap<Integer, Integer> hm = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        hm.put(inorder[0], i);
    }
    return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, hm);
}

private static TreeNode helper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd, HashMap<Integer, Integer> hm) {
    if (inStart > inEnd) {
        return null;
    }
    int inMid = hm.get(postorder[postEnd]);
    TreeNode node = new TreeNode(inorder[inMid]);
    node.left = helper(inorder, postorder, inStart, inMid - 1, postStart, postEnd - (inEnd - inMid) - 1, hm);
    node.right = helper(inorder, postorder, inMid + 1, inEnd, postEnd - (inEnd - inMid), postEnd - 1, hm);
    return node;
}

Check my code on github: preorder-inorder, inorder-postorder.

leetcode 109

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution. At the beginning, I came up idea to use slow and fast point to find the middle element, and generate node. And recursively do left and right side. But this takes O(nlogn) time.

// O(nlogn) solution
public static TreeNode sortedListToBST2(ListNode head) {
    if (head == null) {
        return null;
    }
    if (head.next == null) {
        return new TreeNode(head.val);
    }
    ListNode slow = head, fast = head.next; // pivot should be slow.next. In this way, it is easy to set slow.next = null
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    TreeNode node = new TreeNode(slow.next.val);    // pivot is slow.next
    ListNode next = slow.next.next;
    slow.next = null; // cut the list.
    node.left = sortedListToBST2(head);
    node.right = sortedListToBST2(next);
    return node;
}

However, there is a better O(n) solution. First, count the number of ListNode. And build the AVL tree based on the number.

For 1, 2, 3, 4, 5, 6. mid = 4, left = [1, 2, 3], right = [5, 6]
For 1, 2, 3, 4, 5, 6, 7. mid = 4, left = [1, 2, 3], right = [5, 6, 7]

The code is like below:

// O(n) time, O(logN) solution.
// count number of ListNode, then divide n into 3 parts. And recursively build the AVL tree
// for 1, 2, 3, 4, 5, 6. mid = 4, left = [1, 2, 3], right = [5, 6]
// for 1, 2, 3, 4, 5, 6, 7. mid = 4, left = [1, 2, 3], right = [5, 6, 7]
private ListNode head = null;

public TreeNode sortedListToBST(ListNode head) {
    this.head = head;
    int n = 0;
    ListNode node = head;
    while (node != null) {
        n++;
        node = node.next;
    }
    return helper(n);
}

private TreeNode helper(int n) {
    if (n <= 0) {
        return null;
    }
    int mid = n >> 1;
    TreeNode left = helper(mid);    // left part
    TreeNode node = new TreeNode(head.val);
    head = head.next;
    node.left = left;
    node.right = helper(n - mid - 1);   // right part
    return node;
}

Check my code on github.