[Leetcode] Binary Tree Level order travelsal (normal and zigzag and bottom-up )

一、normal fasion

使用queue記錄上次通路的是記錄的孩子節點

1 public List<List<Integer>> levelOrder(TreeNode root) {
 2     List<List<Integer>> res = new LinkedList<List<Integer>>();
 3     Queue<TreeNode> queue = new LinkedList<TreeNode>();
 4     queue.add(root);
 5     while(!queue.isEmpty()){
 6         int size=queue.size();
 7         List<Integer> listone = new LinkedList<Integer>();
 8         for(int i=0;i<size;i++){
 9             TreeNode tmp = queue.poll();
10             listone.add(tmp.val);
11             if(tmp.left!=null) queue.offer(tmp.left);
12             if(tmp.right!=null) queue.offer(tmp.right);
13         }
14         res.add(listone);
15     }
16     return res;
17 }      

二、zigzag fasion

使用兩個stack交替的記錄孩子資訊，并且使用index标示是從左向右周遊，還是從右向左進行周遊，兩種方式還會影響孩子節點周遊的順序

1 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
 2     List<List<Integer>> res = new LinkedList<List<Integer>>();
 3     Stack [] stacks = new Stack[2];
 4     stacks[0]= new Stack();
 5     stacks[1]= new Stack();
 6     int index=0;
 7     while(!stacks[index%2].isEmpty()){
 8         Stack<Integer> s1 = stacks[index%2];
 9         Stack<Integer> s2 = stacks[(index+1)%2];
10         List<Integer> listone =new LinkedList<Integer>();
11         while(!s1.isEmpty()){
12             TreeNode tmp =s1.pop();
13             listone.add(tmp.val);
14             if(index%2==0){
15                 if(s1.left!=null) s2.push(s1.left);
16                 if(s1.right!=null) s2.push(s1.right);
17             }else{
18                 if(s1.right!=null) s2.push(s1.right);
19                 if(s1.left!=null) s2.push(s1.left);
20             }
21         }
22         res.add(listone);
23         index=(index+1)%2;
24     }
25     return res;
26 }      

 三、bottom up fasion

這裡兩種方法實際上都是normal的方法，隻不過最後要對list當中的層進行reverse

3.1  幾乎和一一樣的方法

1 public List<List<Integer>> levelOrderBottom(TreeNode root) {
 2     List<List<Integer>> res = new LinkedList<List<Integer>>();
 3     Queue<TreeNode> queue = new LinkedList<TreeNode>();
 4     queue.offer(root);
 5     while(!queue.isEmpty()){
 6         List<Integer> listone = new LinkedList<Integer>();
 7         int size= queue.size();
 8         for(int =0;i<size;i++){
 9             TreeNode tmp = queue.poll();
10             listone.add(tmp.val);
11             if(tmp.left!=null) queue.offer(tmp.left);
12             if(tmp.right!=null) queue.offer(tmp.right);
13         }
14         res.add(listone);
15     }
16     //reverse them
17     for(int i=0;i<res.size()/2;i++){
18         List<Integer> tmp = res.get(i);
19         res.set(i,res.get(res.size()-1-i));
20         res.set(res.size()-1-i,tmp);
21     }
22     return res;
23 }      

3.2使用遞歸

1 //using DFS method to store the result of each
 2 private void DFS(List<List<Integer>>res, TreeNode root,int level){
 3     if(res.size()<level){
 4         List<Integer> levelone = new LinkedList<Integer>();
 5         res.add(levelone);
 6     }
 7     List<Integer> levelone = res.get(level-1);
 8     levelone.add(root.val);
 9     DFS(res,root.left,level+1);
10     DFS(res,root.right,level+1);
11 }
12 public List<List<Integer>> levelOrderBottom(TreeNode root) {
13     List<List<Integer>> res = new LinkedList<List<Integer>>();
14     DFS(res,root,1);
15     //reverse them
16     for(int i=0;i<res.size()/2;i++){
17         List<Integer> tmp = res.get(i);
18         res.set(i,res.get(res.size()-1-i));
19         res.set(res.size()-1-i,tmp);
20     }
21     return res;
22 }      

問題:

有沒有不用reverse的方法？

轉載于:https://www.cnblogs.com/deepblueme/p/4732647.html