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

今天药忘吃喽~ 2022-08-26 05:54 39阅读 0赞

**题目：**

**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.][read more on how binary tree is serialized on OJ.]

**分析：**

其实就是二叉树的层次遍历，但是需要把每个层次的数放入到一个ArrayList<Integer>中，最后得到一个存放所有层次结果集合的大集合ArrayList<ArrayList<Integer>> list.

**解题思路：**

居然要层次遍历，那么我们如果一层层放入到queue中，然后取出这一层结点，并把值放入到一个ArrayList<Integer>中，并加入到最终集合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<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        	if (root == null)
        		return result;
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
            
            //初始化先放入根结点到队列中, 为第一层结点
            queue.add(root);
            
            //这里采取一层层的方式加入到队列中
            while (!queue.isEmpty()){
            	ArrayList<TreeNode> tempList = new ArrayList<TreeNode>();
            	ArrayList<Integer> tempValueList = new ArrayList<Integer>();
            	
            	//先取出队列中的所有结点，因为它们是属于同一个层次的,并把这一层结点对应的ArrayList<Integer>值加入到list中。
            	while (!queue.isEmpty()){
            		TreeNode node = queue.remove();
            		tempList.add(node);
            		tempValueList.add(node.val);
            	}
            	list.add(tempValueList);
            	
            	//对刚取出的这一个层次的下一个层次进行遍历加入到队列中。
            	for (int i=0; i<tempList.size(); ++i){
            		TreeNode node = tempList.get(i);
            		if (node.left != null){
            			queue.add(node.left);
            		}
            		if (node.right != null){
            			queue.add(node.right);
            		}
            	}
            }
            
            //结果List的翻转
            for (int i=list.size()-1; 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<ArrayList<Integer>> levelOrderBottom(TreeNode root) {  
            ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();  
               
            if(root == null){  
                return ret;  
            }  
            Queue<TreeNode> queue = new LinkedList<TreeNode>();  
            queue.add(root);  
               
            ArrayList<ArrayList<Integer>> alal = new ArrayList<ArrayList<Integer>>();  
            ArrayList<Integer> al = new ArrayList<Integer>();  
             
            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<Integer>();  
                    currentLevel = nextLevel;  
                    nextLevel = 0;  
                }  
            }  
               
            for(int i=alal.size()-1; i>=0; i--){  
                ret.add(alal.get(i));  
            }  
               
            return ret;  
        } 
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9yZW55dWdhbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70][]

[read more on how binary tree is serialized on OJ.]: http://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/#
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9yZW55dWdhbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019090215274739.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9yZW55dWdhbmcuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70