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