leetCode解题报告|leetCode解题报告之Binary Tree Level Order Traversal II,I(二叉树层次遍历) leetCode解题报告|胖虎LeetCode解题

题目：
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 / \ 920 /\ 157

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

【leetCode解题报告|leetCode解题报告之Binary Tree Level Order Traversal II,I(二叉树层次遍历)】

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