Leetcode （Binary Tree） -- Day 65 & Day 70

Question 1

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Recursive solution:

 1 /**
 2  * Definition for a binary tree node.
 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     List<Integer> result = new ArrayList<Integer>();
12     public List<Integer> preorderTraversal(TreeNode root) {
13         preorderTraversal2(root);
14         return result;
15     }
16     
17     public void preorderTraversal2(TreeNode root){
18         if (root == null)
19             return;
20         result.add(root.val);
21         preorderTraversal(root.left);
22         preorderTraversal(root.right);
23     }
24 }

iterative solution:

 1     public List<Integer> preorderTraversal(TreeNode root) {
 2         List<Integer> result = new ArrayList<Integer>();
 3         if (root == null)
 4             return result;
 5             
 6         Stack<TreeNode> stack = new Stack<TreeNode>();
 7         stack.push(root);
 8         while (!stack.isEmpty()){
 9             TreeNode currentNode = stack.pop();
10             result.add(currentNode.val);
11 
12             if (currentNode.right != null){
13                 stack.push(currentNode.right);
14             }
15             
16             if (currentNode.left != null){
17                 stack.push(currentNode.left);
18             }
19         }
20 
21         return result;
22     }

Question 2

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Recursive solution

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

Iterative solution

 1         public List<Integer> postorderTraversal(TreeNode root) {
 2             Stack<TreeNode> stack = new Stack<TreeNode>();
 3             List<Integer> list = new LinkedList<Integer>();
 4             if(root == null) return list;
 5             stack.push(root);
 6             TreeNode preNode = null;
 7             TreeNode curNode = root;
 8             while(!stack.empty()){
 9                 curNode = stack.peek();
10                 if(curNode.left == null && curNode.right == null || 
11                   preNode != null && (preNode == curNode.left || preNode == curNode.right)){ //prev node is the node has been put in the list before the curNode
12                      stack.pop();
13                      list.add(curNode.val);
14                      preNode = curNode;
15                 }else{
16                     if(curNode.right != null) stack.push(curNode.right);
17                     if(curNode.left != null) stack.push(curNode.left);
18                 }
19             }
20             return list;
21     
22         }

Question 3

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

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

Iterative

 1 public class Solution {
 2     List<Integer> ans = new ArrayList<>();
 3     public List<Integer> inorderTraversal(TreeNode root) {
 4         Stack<TreeNode> stack = new Stack<>();
 5         TreeNode cur = root;
 6         while (!stack.isEmpty() || cur != null) {
 7             while (cur != null) {
 8                 stack.push(cur);
 9                 cur = cur.left;
10             }
11             cur = stack.pop();
12             ans.add(cur.val);
13             cur = cur.right;
14         }
15         return ans;
16     }
17     
18 }

Recursive

 1 public class Solution {
 2     public List<Integer> inorderTraversal(TreeNode root) {
 3         List<Integer> result = new ArrayList<Integer>();
 4         inorderTraversal(root, result);
 5         return result;
 6     }
 7     
 8     public void inorderTraversal(TreeNode root, List<Integer> result){
 9         if (root == null)
10             return ;
11         inorderTraversal(root.left, result);
12         result.add(root.val);
13         inorderTraversal(root.right, result);
14     }
15 }

Question 4

Construct Binary Tree from Preorder and Inorder Traversal

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

Note:
You may assume that duplicates do not exist in the tree.

 1 public class Solution {
 2     public TreeNode buildTree(int[] preorder, int[] inorder) {
 3         
 4         int preStart = 0, preEnd = preorder.length-1;
 5         int inStart = 0, inEnd = inorder.length-1;
 6         return buildTree(preorder, preStart, preEnd, inorder, inStart, inEnd);
 7     }
 8     
 9     public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd){
10         if (preStart > preEnd || inStart > inEnd){
11             return null;
12         }
13         
14         int val = preorder[preStart];
15         TreeNode cur = new TreeNode(val);
16         
17         int k = 0;
18         for (int i = 0; i < inorder.length; i ++){
19             if (val == inorder[i]){
20                 k = i;
21                 break;
22             }
23         }
24         
25         cur.left = buildTree(preorder, preStart + 1, preStart+k-inStart, inorder, inStart, k-1);
26         cur.right = buildTree(preorder, preStart+k-inStart+1, preEnd, inorder, k+1, inEnd);
27         
28         return cur;
29     }
30 }

Question 5

Construct Binary Tree from Inorder and Postorder Traversal

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

Note:
You may assume that duplicates do not exist in the tree.

 1 public class Solution {
 2     public TreeNode buildTree(int[] inorder, int[] postorder) {
 3         if (inorder.length < 1 || inorder.length < 1)
 4             return null;
 5         int inStart = 0, inEnd = inorder.length-1;
 6         int poStart = 0, poEnd = postorder.length-1;
 7         
 8         return buildTreeHelper(inorder, inStart, inEnd, postorder, poStart, poEnd);
 9     }
10     
11     public TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int poStart, int poEnd){
12         if (poStart > poEnd ||inStart > inEnd)
13             return null;
14         
15         TreeNode cur = new TreeNode(postorder[poEnd]);
16         int k = 0;
17         for (int i = inorder.length - 1; i >= 0; i --){
18             if (inorder[i] == cur.val){
19                 k = i;
20                 break;
21             }
22         }
23         
24         int leftTreeSize = k - inStart;
25         int rightTreeSize = inEnd - k;
26         
27         cur.right = buildTreeHelper(inorder, k+1, inEnd, postorder, poEnd-(inEnd-k), poEnd-1);
28         cur.left = buildTreeHelper(inorder, inStart, k-1, postorder, poStart, poStart + leftTreeSize - 1);
29         
30         return cur;
31         
32     }
33 }

Question 6

Binary Tree Level Order Traversal

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},

return its level order traversal as:

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

confused what "{1,#,2,3}" means?

 1 public List<List<Integer>> levelOrder(TreeNode root) {
 2         List<List<Integer>> result = new ArrayList<List<Integer>>();
 3         if (root == null)
 4             return result;
 5         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 6         queue.add(root);
 7         
 8         while(queue.size() > 0){
 9             int size = queue.size();
10             List<Integer> temp = new ArrayList<Integer>();
11             while(size-- > 0){
12                 TreeNode cur = queue.poll();
13                 temp.add(cur.val);
14                 if (cur.left != null){
15                     queue.add(cur.left);
16                 }
17                 if (cur.right != null){
18                     queue.add(cur.right);
19                 }
20             }
21             
22             result.add(temp);
23         }
24         return result;
25     }

Question 7

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:
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]
]

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

 1 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
 2         List<List<Integer>> result = new ArrayList<List<Integer>>();
 3         if (root == null)
 4             return result;
 5         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 6         queue.add(root);
 7         boolean order = false;
 8         while (!queue.isEmpty()){
 9             int size = queue.size();
10             ArrayList<Integer> nest = new ArrayList<Integer>();
11             while(size-- > 0){
12                 TreeNode cur = queue.poll();
13                 if (order)
14                     nest.add(0,cur.val);
15                 else
16                     nest.add(cur.val);
17                 if (cur.left != null){
18                     queue.add(cur.left);
19                 }
20                 if (cur.right != null){
21                     queue.add(cur.right);
22                 }
23             }
24             order = !order;
25             result.add(nest);
26         }
27         return result;
28     }

Question 8

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its bottom-up level order traversal as:

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

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

 1     public List<List<Integer>> levelOrderBottom(TreeNode root) {
 2         List<List<Integer>> result = new ArrayList<List<Integer>>();
 3         if (root == null)
 4             return result;
 5         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 6         queue.add(root);
 7         while (!queue.isEmpty()){
 8             int size = queue.size();
 9             List<Integer> nest = new ArrayList<Integer>();
10             while(size -- > 0){
11                 TreeNode cur = queue.poll();
12                 nest.add(cur.val);
13                 if (cur.left != null)
14                     queue.add(cur.left);
15                 if (cur.right != null)
16                     queue.add(cur.right);
17             }
18             result.add(0,nest);
19         }
20         return result;
21     }