显示标签为“Tree”的博文。显示所有博文
显示标签为“Tree”的博文。显示所有博文

2014年4月14日星期一

Populating Next Right Pointers in Each Node

Problem:
Given a binary tree
    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Analysis:
The first thought occurs to me is the level order traversal, but this problem requires constant space. Level order traversal requires a queue. The recursive method is fast and easy to under stand. Let's assume that the current node is connected with its next node. Its left child's next node is its right child. Its right child's next node is its next node's left child. The space is O(N).

Solution:

1:  /**  
2:   * Definition for binary tree with next pointer.  
3:   * public class TreeLinkNode {  
4:   *   int val;  
5:   *   TreeLinkNode left, right, next;  
6:   *   TreeLinkNode(int x) { val = x; }  
7:   * }  
8:   */  
9:  public class Solution {  
10:    public void connect(TreeLinkNode root) {  
11:      if(root==null)  
12:       return;  
13:      if(root.left!=null)  
14:       root.left.next=root.right;  
15:      if(root.right!=null)  
16:       root.right.next=root.next==null?null:root.next.left;  
17:      connect(root.left);  
18:      connect(root.right);  
19:    }  
20:  }  

2014年4月9日星期三

Binary Tree Level Order Traversal

Problem:
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]
Analysis:
Method 1:
Use two queues. One to record the current level, the other keeps record of the next level. Iterate the current level add the children of each nodes in current level to the next level queue. After the current level queue becomes empty, assign the next level to current level.

Method 2:
Use one queue. Use two counters, one counts the current level number of nodes the other counts the next level number of nodes. Each time remove from the linked list, current level number of nodes decrease and add next level number of nodes accordingly.  When current level counter reaches 0, add current level to the final ArrayList. Then next level counter becomes current level counter. Have to note that the ArrayList is the reference type in Java, if clear the ArraryList<Integer> after adding it to the ArraryList<ArraryList<Integer>> then reuse it, it would clear what's inside the ArraryList<ArraryList<Integer>>. So I created another instance every time current level nodes reaches 0.

Solution:
1. Two Queues
1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {  
12:      ArrayList<ArrayList<Integer>> alResult=new ArrayList<ArrayList<Integer>>();  
13:      if(root==null)  
14:        return alResult;  
15:      LinkedList<TreeNode> currLevel=new LinkedList<TreeNode>();  
16:      currLevel.add(root);  
17:      while(!currLevel.isEmpty())  
18:      {  
19:        ArrayList<Integer> alLevel=new ArrayList<Integer>();  
20:        LinkedList<TreeNode> nextLevel=new LinkedList<TreeNode>();  
21:        while(!currLevel.isEmpty())  
22:        {  
23:          TreeNode currNode=currLevel.remove();  
24:          alLevel.add(currNode.val);  
25:          if(currNode.left!=null) nextLevel.add(currNode.left);  
26:          if(currNode.right!=null) nextLevel.add(currNode.right);  
27:        }  
28:        currLevel=nextLevel;  
29:        alResult.add(alLevel);  
30:      }  
31:      return alResult;  
32:    }  
33:  }  
2. One queue
1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {  
12:      ArrayList<ArrayList<Integer>> alResult=new ArrayList<ArrayList<Integer>>();  
13:      ArrayList<Integer> alLevel=new ArrayList<Integer>();  
14:      LinkedList<TreeNode> currLevel=new LinkedList<TreeNode>();  
15:      if(root==null)  
16:        return alResult;  
17:      int curr=1;  
18:      int next=0;  
19:      currLevel.add(root);  
20:      while(!currLevel.isEmpty())  
21:      {  
22:        TreeNode currNode=currLevel.remove();  
23:        curr--;  
24:        alLevel.add(currNode.val);  
25:        if(currNode.left!=null)   
26:        {  
27:          currLevel.add(currNode.left);  
28:          next++;  
29:        }  
30:        if(currNode.right!=null)   
31:        {  
32:          currLevel.add(currNode.right);  
33:          next++;  
34:        }  
35:        if(curr==0)  
36:        {  
37:          curr=next;  
38:          next=0;  
39:          alResult.add(alLevel);  
40:          ArrayList<Integer> alLevelTemp=new ArrayList<Integer>();  
41:          alLevel=alLevelTemp;  
42:        }  
43:      }  
44:      return alResult;  
45:    }  
46:  }  

2014年4月8日星期二

Binary Tree Postorder Traversal

Problem:
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].
Analysis:
The most difficult one among preorder, inorder and postorder traversals. The difficulty lays in that after going down to left it will go right, storing the parent node is a problem. Use one more stack to assist push nodes in reserve order of postorder to the final stack.
Steps:
1.Push the root node to the temp stack.
2.Pop node c from temp stack.
3.If c has left child push it to final stack.If c has right child push it to final stack.
4.Push c to final stack.
5.Repeat 2-4 until temp stack is empty.
6.Print final stack.
Solution:
1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<Integer> postorderTraversal(TreeNode root) {  
12:      ArrayList<Integer> result=new ArrayList<Integer>();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> t=new Stack<TreeNode>();//temp stack   
16:      Stack<TreeNode> r=new Stack<TreeNode>();//result stack  
17:      t.push(root);  
18:      while(!t.isEmpty())  
19:      {  
20:       TreeNode current=t.pop();  
21:        if(current.left!=null) t.push(current.left);  
22:        if(current.right!=null) t.push(current.right);  
23:        r.push(current);  
24:      }  
25:      while(!r.isEmpty())  
26:      {  
27:       TreeNode current=r.pop();  
28:        result.add(current.val);  
29:      }  
30:      return result;  
31:    }  
32:  }  

2014年4月7日星期一

Binary Tree Inorder Traversal

Problem:
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,3,2].
Analysis:
The definition of inorder traversal is visit the left node first, the parent node second and the right node last. Iterative implementation of inorder traversal is more difficult than preorder traversal. We need to consider how to visit the left most node and keep track of the trace.
1. Push the root node to the stack.
2. Set the left child of the current node to the current node.
3. Continue 1,2 until current node is null.
4. If current node is not null.
   1). Pop current node from the stack and write it.
   2). Set the right child of the current node to the current node. go to 2.
5. If the stack is empty return. 
Solution:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<Integer> inorderTraversal(TreeNode root) {  
12:      ArrayList<Integer> result=new ArrayList<Integer>();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> stack=new Stack<TreeNode>();  
16:      TreeNode current=root;  
17:      while(true)  
18:      {  
19:        if(current!=null)//iterate left until there is no left node at all       
20:        {  
21:         stack.push(current);  
22:         current=current.left;  
23:        }  
24:        else  
25:        {  
26:          if(!stack.isEmpty())  
27:          {  
28:            current=stack.pop();  
29:            result.add(current.val);  
30:            current=current.right;//have visited the left and the parent node, time to visit the right one.  
31:          }  
32:          else  
33:           break;  
34:        }  
35:      }  
36:      return result;  
37:    }  
38:  }  

2014年4月3日星期四

Binary Tree Preorder Traversal

Problem:
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].
Analysis:
Use stack to temporarily store the nodes. Because stack is FILO, push order is from right to left. I spent about half an hour thinking the idea. It was my first time implement the preorder traversal. 
Solution:
1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList preorderTraversal(TreeNode root) {  
12:         ArrayList result = new ArrayList();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> nodeStack=new Stack<TreeNode>();  
16:      nodeStack.push(root);  
17:      while(!nodeStack.isEmpty())  
18:      {  
19:        TreeNode current=nodeStack.pop();  
20:        if(current.right!=null) nodeStack.push(current.right);  
21:        if(current.left!=null) nodeStack.push(current.left);  
22:        result.add(current.val);  
23:      }  
24:      return result;  
25:    }  
26:  }  

2014年3月31日星期一

Unique Binary Search Trees

Problem:
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         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
Analysis:

Refer http://blog.joysword.com/en/posts/2014/02/unique_binary_search_trees/.

Solution:

 public class Solution {  
   public int numTrees(int n) {  
     if(n==0)  
      return 1;  
     if(n==1)  
      return 1;  
     int num=0;  
       for(int j=1;j<=n;j++)  
       {  
         num+=numTrees(j-1)*numTrees(n-j);  
       }  
      return num;  
   }  
 }