leetCode解題報告之Binary Tree Level Order Traversal II,I(二叉樹層次遍歷)

題目：

Binary Tree Level Order Traversal II（由於Binary Tree Level Order Traversal I 這個題目只是在II的基礎上少了一步最後的翻轉result list而已，所以我就不貼出它的代碼了）

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

    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.

分析：

其實就是二叉樹的層次遍歷，但是需要把每個層次的數放入到一個ArrayList中，最後得到一個存放所有層次結果集合的大集合ArrayList> list.

解題思路：

居然要層次遍歷，那麼我們如果一層層放入到queue中，然後取出這一層結點，並把值放入到一個ArrayList中，並加入到最終集合list中，接著我們把這一層的孩子結點，即下一層的結點再放入到queue中，這樣直到queue為empty的時候，我們便把所有層次都遍歷完畢了,這樣子我們將 list 進行翻轉，便得到了題目想要的結果了！！

AC代碼1：（436ms）

package cn.xym.leetcode.twosum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}
public class Solution {
    public ArrayList> levelOrderBottom(TreeNode root) {
    	ArrayList> result = new ArrayList>();
    	if (root == null)
    		return result;
        Queue queue = new LinkedList();
        ArrayList> list = new ArrayList>();
        
        //初始化先放入根結點到隊列中, 為第一層結點
        queue.add(root);
        
        //這裡采取一層層的方式加入到隊列中
        while (!queue.isEmpty()){
        	ArrayList tempList = new ArrayList();
        	ArrayList tempValueList = new ArrayList();
        	
        	//先取出隊列中的所有結點，因為它們是屬於同一個層次的,並把這一層結點對應的ArrayList值加入到list中。
        	while (!queue.isEmpty()){
        		TreeNode node = queue.remove();
        		tempList.add(node);
        		tempValueList.add(node.val);
        	}
        	list.add(tempValueList);
        	
        	//對剛取出的這一個層次的下一個層次進行遍歷加入到隊列中。
        	for (int i=0; i=0; --i){
        	result.add(list.get(i));
        }
        return result;
    }
}

AC代碼2(網友提供)：（472ms）

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList> levelOrderBottom(TreeNode root) {  
        ArrayList> ret = new ArrayList>();  
           
        if(root == null){  
            return ret;  
        }  
        Queue queue = new LinkedList();  
        queue.add(root);  
           
        ArrayList> alal = new ArrayList>();  
        ArrayList al = new ArrayList();  
         
        int currentLevel = 1;  
        int nextLevel = 0;  
           
        while( !queue.isEmpty() ){  
            TreeNode cur = queue.remove();  
            currentLevel--;  
            al.add(cur.val);  
               
            if(cur.left != null){  
                queue.add(cur.left);  
                nextLevel++;  
            }  
            if(cur.right != null){  
                queue.add(cur.right);  
                nextLevel++;  
            }  
               
            if(currentLevel == 0){  
                alal.add(al);  
                al = new ArrayList();  
                currentLevel = nextLevel;  
                nextLevel = 0;  
            }  
        }  
           
        for(int i=alal.size()-1; i>=0; i--){  
            ret.add(alal.get(i));  
        }  
           
        return ret;  
    } 
}