! ? Leetcode - Recover Binary Search Tree

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization: The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode prev;
    
    public void recoverTree(TreeNode root) {
        if(root == null)    return;
        
        ArrayList<TreeNode> wrongList = new ArrayList<TreeNode>();
        prev = null;
        inOrder(root, wrongList);
        
        int tmp = wrongList.get(0).val;
        wrongList.get(0).val = wrongList.get(wrongList.size() - 1).val;
        wrongList.get(wrongList.size() - 1).val = tmp;

    }
    
    public void inOrder(TreeNode node, ArrayList<TreeNode> wrongList) {
        if(node == null)    return;
        
        inOrder(node.left, wrongList);
        
        // if found
        if(prev != null && prev.val > node.val) {
            if(!(wrongList.contains(prev))) wrongList.add(prev);
            if(!(wrongList.contains(node))) wrongList.add(node);
        }
        prev = node;
        
        inOrder(node.right, wrongList);
    }
}

Reference:
1. http://jane4532.blogspot.com/2013/07/recover-binary-search-treeleetcode.html
2. https://gist.github.com/guolinaileen/5125340

Leetcode - Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(num == null || num.length == 0) return null;
        
        int start = 0, end = num.length - 1;

        TreeNode root = buildTree(num, start, end);
        
        return root;
    }
    
    public TreeNode buildTree(int[] num, int start, int end) {
        if(start > end) return null;
        
        int mid = (start + end) / 2;
        
        // build left sub tree
        TreeNode left = buildTree(num, start, mid - 1);
        // build root of the subtree
        TreeNode node = new TreeNode(num[mid]);
        node.left = left;
        // build right sub tree
        node.right = buildTree(num, mid + 1, end);
        
        return node;
    }
}

Leetcode - Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    static ListNode head;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)    return null;
        this.head = head;
        
        // get list length
        int len = 0;
        ListNode ln = head;
        while(ln != null){
            len++;
            ln = ln.next;
        }   
        
        return sortedListToBST(0, len - 1);
    }
    
    // build bottom-to-top
    public TreeNode sortedListToBST(int start, int end) {
        // if finished (root)
        if(start > end) return null;
        
        // get mid val
        int mid = (start + end) / 2;
        
        // build left sub tree
        TreeNode left = sortedListToBST(start, mid - 1);
        // build root node
        TreeNode root = new TreeNode(head.val);
        root.left = left;
        // move to next node to build right sub tree
        head = head.next;
        root.right = sortedListToBST(mid + 1, end);
        
        return root;
    }
}

Reference: http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

Java - implements vs. extends

extends is for extending a class.

implements is for implementing an interface

Example:

implements:

public interface ExampleInterface{
    public void do();
    public String doThis(int number);
 }

 public class sub implements ExampleInterface{
     public void do(){
       //specify what must happen
     }

     public String doThis(int number){
       //specfiy what must happen
     }
 }

extends:

public class SuperClass{
    public int getNb(){
         //specify what must happen
        return 1;
     }

     public int getNb2(){
         //specify what must happen
        return 2;
     }
 }

 public class SubClass extends SuperClass{
      //you can override the implementation
      @Override
      public int getNb2(){
        return 3;
     }
 }

result:

Subclass s = new SubClass();
  s.getNb(); //returns 1
  s.getNb2(); //returns 3

  SuperClass sup = new SuperClass();
  sup.getNb(); //returns 1
  sup.getNb2(); //returns 2

Reference: http://stackoverflow.com/questions/10839131/implement-vs-extends-when-to-use-whats-the-difference

Leetcode - Merge Intervals

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        
        if(intervals == null) return intervals;
        int len = intervals.size();
        if(len == 0 || len == 1)    return intervals;
        
        // sort the input by start value
        Collections.sort(intervals, new IntervalComparator());
        
        Interval a = intervals.get(0);
        for(int i = 1; i < len; i++) {
            Interval b = intervals.get(i);
            // if mergeable, merge a and b.
            if(a.end >= b.start) {
                a = new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
            }
            // if not mergeable, move to the next, reset the a node.
            else {
                res.add(a);
                a = b;
            }
        }
        res.add(a);
        return res;
        
    }
}

class IntervalComparator implements Comparator<interval>
{
    public int compare(Interval a, Interval b) {
        return a.start - b.start;
    }
}

About Array, ArrayList, LinkedList

Array:

1. Fixed length data structure, cannot change length once created

2. Cannot user Generics.

3. All kinds of Array provideslength variable which denotes length of Arra, array.length to get length

4. Allow both primitives and Objects. (int[], Object[])

5. You can simply use assignment operator to store element into Array. (int[] i = new int[10]; int[1] = 1;)

6. Must provide size when init.

ArrayList:

1. Dynamic length, however, re-size is slow (create a new array and copying content from old to new)

2. Allows to use Generics to ensure type safe.

3. All kinds of Array provideslength variable which denotes length of Arra, arraylist.size() to get size

4. Only allow Objects but not primitives. (ArrayList)

5. Java provides add() method to insert element into ArrayList.

6. Do not need to provide size when init.


--------------------------------------------------
ArrayList:
1. Index based data-structure. O(1) for search, get(index).

2. Add element, O(1) if doesn't trigger re-size of the array. O(log(n)) if re-size.

3. O(n) for remove and insert, need to re-arrange all elements.

4. Less memory overhead, because ArrayList each index only holds actual object (data).


LinkedList:

1. O(n) for search(get) element.

2. O(1) for add element.

3. For insert or remove element, still need O(n) to travers to that pointer (can traverse from either direction based upon proximity)

4. More memory overhead, because LinkedList each node holds both data and address of next and previous node.

Leetcode - Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

public class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0)
            return false;
            
        boolean res = false;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] == word.charAt(0)) {
                    char[][] tmp = board;
                    tmp[i][j] = 0;
                    if(ifFound(tmp, i, j, word, 1)) return true;
                }
            }
        }
        
        return res;
    }
    
    public boolean ifFound(char[][] b, int i, int j, String s, int idx) {
        boolean res = false;
        if(idx == s.length()) return true;
        
        char c = s.charAt(idx);
        // top
        if(i- 1 >= 0 && b[i - 1][j] == c) {
            if(idx == s.length() - 1) return true;
            
            char[][] tmp = b;
            tmp[i - 1][j] = 0;
            if(ifFound(tmp, i - 1, j, s, idx + 1))  return true;
        }
        // bottom
        if(i + 1 < b.length && b[i + 1][j] == c) {
            if(idx == s.length() - 1) return true;
            
            char[][] tmp = b;
            tmp[i + 1][j] = 0;
            if(ifFound(tmp, i + 1, j, s, idx + 1))    return true;
        }
        // left
        if(j - 1 >= 0 && b[i][j - 1] == c) {
            if(idx == s.length() - 1) return true;
            
            char[][] tmp = b;
            tmp[i][j - 1] = 0;
            if(ifFound(tmp, i, j - 1, s, idx + 1))    return true;
        }
        // right
        if(j + 1 < b[0].length && b[i][j + 1] == c) {
            if(idx == s.length() - 1) return true;
            
            char[][] tmp = b;
            tmp[i][j + 1] = 0;
            if(ifFound(tmp, i, j + 1, s, idx + 1))    return true;
        }
        
        return res;
    }
}

Leetcode - Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL 

 /**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)    return;
        
        ArrayList<TreeLinkNode> q = new ArrayList<TreeLinkNode>();
        
        q.add(root);
        
        while(!q.isEmpty()) {
            ArrayList<TreeLinkNode> next = new ArrayList<TreeLinkNode>();
            
            for(int i = 0; i < q.size(); i++) {
                TreeLinkNode node = q.get(i);
                if(node.left != null)   next.add(node.left);
                if(node.right != null)  next.add(node.right);
                
                if(i == q.size() - 1)   node.next = null;
                else    node.next = q.get(i + 1);
            }
            
            q = new ArrayList<TreeLinkNode>(next);
        }
    }
}

Leetcode - Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int res = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        if(root == null)    return 0;
        
        res = Integer.MIN_VALUE;
        
        getMaxSum(root);
        
        return res;
    }
    
    public int getMaxSum(TreeNode node) {
        if(node == null)    return 0;
        
        int left = getMaxSum(node.left);
        int right = getMaxSum(node.right);
        
        int thisSum = node.val;
        
        if(left > 0)    thisSum += left;
        if(right > 0)   thisSum += right;
        
        res = Math.max(res, thisSum);
        
        // only need return the largest subtree with this node val
        return node.val + Math.max(0, Math.max(left, right));
    }
}

First Post

solve one issue per day