Validate Binary Search Tree， Unique Binary Search Trees, Unique Binary Search Trees II, Binary Tree Preorder Traversal,Binary Tree Inorder Traversal ,Binary Tree Postorder Traversal, Binary Tree Zigzag Level Order Traversal, Binary Search Tree Iterator

Posted on 2015-04-16   |   In 刷题   |  

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Brute force Solution

Inorder traversal, then compare each value…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isValidBST(TreeNode root) {
    if(root==null) return true;
    LinkedList<Integer> p = new LinkedList<Integer>();
    inorder(root, p);
    for (int j =0;j< p.size() - 1;j++) {
        if(p.get(j)>=p.get(j+1))
        return false;
    }
    return true;
}
private void inorder(TreeNode r, LinkedList<Integer> p){
    if(r==null) return;
    inorder(r.left,p);
    p.add(r.val);
    inorder(r.right,p);
}

Or use static variable to store the previous val:

1
2
3
4
5
6
7
8
9
10
public static int pre = Integer.MIN_VALUE; 
public boolean isValidBST(TreeNode root) {
    if(root==null) return true;
    if(!isValidBST(root.left)) return false;
    if(root.val<=pre) return false;
    System.out.println(pre);
    pre=root.val;
    if(!isValidBST(root.right)) return false;
    return true;
}

Recursive/MinMax Solution

At each node we must satisty

  • left subtree max value must not exceed cur.val
  • right subtree min value must not be lower than cur.val
1
2
3
4
5
6
7
8
9
public boolean isValidBST(TreeNode root) {
    return dfs(root, (long)Integer.MIN_VALUE-1,(long)Integer.MAX_VALUE+1);
}
private boolean dfs(TreeNode r,long minv, long maxv){
    if(r==null) return true;
    if(r.val>=maxv ||r.val<=minv) return false;
    return  dfs(r.left, minv, r.val) && dfs(r.right, r.val, maxv);
}

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.

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

DP Solution

  • Define c[i] as the number of unique binary tree possibly generated with [0….i]
  • A tree with i as its root, left subtree is consist of [1…i-1], right subtree is consist of [i+1…n]
  • c[0] = 0 ; c[1]=1 ; c[2] = c[0]c[1] //1 as root + c[1]c[0] //0 as root; c[3] = c[0] c[2] //1 as root + c[1] c[1] //2 as root + c[2] * c[0] //3 as root
  • Ct+1 += Ci*Ct-i(0<= i <= t)
  • Ct += Ci*t-1-i(0<=i<=t-1, 1<=t<=n)
1
2
3
4
5
6
7
8
9
10
11
12
public int numTrees(int n) {
        if(n == 0||n == 1)
            return 1;
        int[] C = new int[n+1];
        C[0] = 1;
    for(int t=1;t<=n;t++){  
        for(int i=0;i<=t-1;i++){  
            C[t] += C[i]*C[t-1-i];  
        }  
    }
        return C[n];
    }

Unique Binary Search Trees II

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

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

DFS Solution

Similar to I, we pick (1…n) as root, recursivly get all left and right subtrees.
We pick one from left subtree and one from right subtree, attach them to current root and return all the possibilities.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ArrayList<TreeNode> generateTrees(int n) {
    return buildTrees(1,n);
    
}
public ArrayList<TreeNode> buildTrees(int min, int max){
    ArrayList<TreeNode> res = new ArrayList<TreeNode>();
    if(min>max){res.add(null); return res;}
    for(int i=min;i<=max;i++){
        ArrayList<TreeNode> l = buildTrees(min,i-1);
        ArrayList<TreeNode> r = buildTrees(i+1,max);
        for(TreeNode j: l){
            for(TreeNode k:r){
                TreeNode root =  new TreeNode(i);
                root.left = j;
                root.right = k;
                res.add(root);
            }
        }
    }
    return res;
}

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
6
   1
    \
     2
    /
   3
return [1,2,3].

Recursive Solution

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    preorder(root, res);
    return res;
}
private void preorder(TreeNode n, ArrayList<Integer> res){
    if(n==null) return;
    res.add(n.val);
    preorder(n.left,res);
    preorder(n.right,res);
}

Iterative Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    Stack<TreeNode> stk =new Stack<TreeNode>();
    if(root==null) return res; //别忘了这句...
    stk.push(root);
    while(!stk.isEmpty()){
        TreeNode tmp = stk.pop();
        res.add(tmp.val);
        if(tmp.right!=null) stk.push(tmp.right);
        if(tmp.left!=null) stk.push(tmp.left);
    }
    return res;
}

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
6
   1
    \
     2
    /
   3
return [1,3,2].

Iterative Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res= new ArrayList<Integer>();
        Stack<TreeNode> stk=new Stack<TreeNode>();
        if(root==null) return res;
        stk.push(root);
        while(!stk.isEmpty()){
            TreeNode tmp = stk.pop();
            if(tmp == null){
                res.add(stk.pop().val);
            }
            else{
                if(tmp.right!=null){stk.push(tmp.right);}
                stk.push(tmp);
                stk.push(null);
                if(tmp.left!=null){stk.push(tmp.left);}
            }
        }
        return res;

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
6
   1
    \
     2
    /
   3
return [3,2,1].

Recursive Solution

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    postorder(root, res);
    return res;
}
private void postorder(TreeNode n, ArrayList<Integer> res){
    if(n==null) return;
    postorder(n.left,res);
    postorder(n.right,res);
    res.add(n.val);
}

Iterative Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    Stack<TreeNode> stk =new Stack<TreeNode>();
    if(root==null) return res; 
    stk.push(root);
    while(!stk.isEmpty()){
        TreeNode tmp = stk.pop();
        if(tmp==null) res.add(stk.pop().val);
        else{
            stk.push(tmp);
            stk.push(null);
            if(tmp.right!=null) stk.push(tmp.right);
            if(tmp.left!=null) stk.push(tmp.left);
        }
    }        
    return res;
}

Binary Tree Zigzag Level Order Traversal

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:

1
2
3
4
5
6
7
8
9
10
11
12
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Recursive Solution

  • Simple DFS, check height%2 each level
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ArrayList<List<Integer>> zigzagLevelOrder(TreeNode root) {
 ArrayList<List<Integer>> res = new ArrayList();
 if(root==null) return res;
 dfs(root, res, 0);
 return res;
 }
private void dfs(TreeNode r, ArrayList<List<Integer>> res, int h){
    if(r==null) return;
    if(h>res.size()-1){
        res.add(new ArrayList<Integer>());
    }
    if(h%2==1){
        res.get(h).add(0,r.val);
    }  
    else{
        res.get(h).add(r.val);
    }
    dfs(r.left, res, h+1);
    dfs(r.right,res,h+1);
}

Iterative Solution

  • a queue to store nodes in BFS order
  • a boolean value to decide insert order in each level list
  • each new level, set poopsite direction, clear list and add to result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public ArrayList<List<Integer>> zigzagLevelOrder(TreeNode root) {
  ArrayList<List<Integer>> res = new ArrayList();
  if(root==null) return res;
  Queue<TreeNode> q = new LinkedList<TreeNode>();
  List<Integer> tmp = new ArrayList<Integer>();
  q.offer(root);
  int size = q.size();
  boolean l2r = true;
  while(!q.isEmpty()){
      TreeNode cur = q.poll();
      size--;
      if(l2r){
         tmp.add(cur.val);
         }
      else{
         tmp.add(0,cur.val);
      }
      if(cur.left!=null) q.offer(cur.left);
      if(cur.right!=null) q.offer(cur.right);
      if(size==0){
          res.add(new ArrayList(tmp));
          l2r=!l2r;
          tmp.clear();
          size = q.size();
      }
  }
  return res;
  }

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution

  • Use one Array to store the inorder traversal of nodes 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ArrayDeque<TreeNode> arr;
public BSTIterator(TreeNode root) {
    arr = new ArrayDeque<TreeNode>();
    inorder(root, arr);
}
private void inorder(TreeNode root, ArrayDeque<TreeNode> arr){
    if(root==null) return;
    inorder(root.left, arr);
    arr.add(root);
    inorder(root.right,arr);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
    return !arr.isEmpty();
}
/** @return the next smallest number */
public int next() {
    if(hasNext()) return arr.poll().val;
    else return -1;
}

O(1) Time O(h) Memory Solution

  • Dissect inorder into two parts
  • push root’s all left children into stack
  • upon calling next(), pop one node and push all right child’s left child into stack 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Stack<TreeNode> stk;
public BSTIterator(TreeNode root) {
    stk = new Stack<TreeNode>();
    while(root!=null){
        stk.push(root);
        root=root.left;
    }
   
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
    return !stk.isEmpty();
}
/** @return the next smallest number */
public int next() {
    if(!stk.isEmpty())
        {TreeNode tmp = stk.pop();
         int res=tmp.val;
         if(tmp.right!=null){
             TreeNode node = tmp.right;
             while(node!=null){
                 stk.push(node);
                 node=node.left;
             }
         }
         return res;
        }
        else return -1;
}
#Tree #Recursion #Stack
Niccolo Paganini Selected Works
Maximum Subarray, Maximum Product Subarray