首页 > 试题广场 >

二叉树层序遍历 ii

[编程题]二叉树层序遍历 ii

热度指数：15989 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个二叉树，返回该二叉树由底层到顶层的层序遍历，（从左向右，从叶子节点到根节点，一层一层的遍历）

例如：

给定的二叉树是{3,9,20,#,#,15,7},

该二叉树由底层到顶层层序遍历的结果是

[[15,7],[9,20],[3]]

示例1

输入

{1,#,2}

输出

[[2],[1]]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

悟Kong

用栈存储层序，再输出

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> List1=new ArrayList<ArrayList<Integer>>();
        if(root==null)
            return List1;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        Stack<ArrayList<Integer>> stack=new Stack<ArrayList<Integer>>();
        queue.add(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> list1=new ArrayList<Integer>();
            int count=queue.size();
            while(count>0){
                TreeNode temp=queue.poll();
                list1.add(temp.val);
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
                count--;
            }
            stack.add(list1);
        }
        while(!stack.empty()){
            List1.add(stack.pop());
        }
        return List1;
    }
}

发表于 2020-03-06 17:29:47 回复(0)

Java

key、L

只比binary-tree-level-order-traversal多了一句话。。Collections.reverse(lists)，，利用操作集合的工具类Collections中的reverse方法对lists进行反转

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if(root == null)
            return lists;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty())
        {
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++)
            {
                TreeNode node = queue.poll();
                if(node.left != null)
                    queue.offer(node.left);
                if(node.right != null)
                    queue.offer(node.right);
                list.add(node.val);
            }
            lists.add(list);
        }
        Collections.reverse(lists);
        return lists;
    }
}

发表于 2020-01-16 16:43:16 回复(0)

Java

放学后我不走~

下至上和上至下层次遍历，改一行代码就好

import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Queue;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
        if(root==null)
            return lists;
        ArrayList<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        Queue<TreeNode> temp = new LinkedList<TreeNode>();
        q.add(root);
        while(!q.isEmpty() || !temp.isEmpty()){
            list = new ArrayList<Integer>();
            while(!q.isEmpty()){
                root = q.remove();
                list.add(root.val);
                if(root.left!=null)
                    temp.add(root.left);
                if(root.right!=null)
                    temp.add(root.right);
            }
            //如果是上至下层次遍历
            //lists.add(list);
            //如果是下至上层次遍历，则将list这一层插在最前面
            lists.add(0, list);
            while(!temp.isEmpty())
                q.add(temp.remove());
        }
        return lists;
}
}

编辑于 2018-08-31 20:28:40 回复(0)

Java

七仔0312

巧妙利用队列的入队和出队的顺序

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null) 
                    queue.add(node.right);
            }
            result.add(0, list);
        }
        return result;
    }
}

发表于 2018-03-16 13:10:28 回复(1)

Java

明耀

/**

* Definition for binary tree

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

import java.util.*;

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>();

queue.add(root);

queue.add(null);

ArrayList<Integer> list=new ArrayList<Integer>();

while(!queue.isEmpty())

{

TreeNode tmp=queue.poll();

if(tmp==null)

{

result.add(0,list);

list=new ArrayList<Integer>();

if(queue.isEmpty())

break;

queue.add(null);

}

else

{

list.add(tmp.val);

if(tmp.left!=null)

{

queue.add(tmp.left);

}

if(tmp.right!=null)

{

queue.add(tmp.right);

}

return result;

}

发表于 2017-08-28 11:29:01 回复(0)

Java

阿拉要洗澡

/**

* Definition for binary tree

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

import java.util.ArrayList;

import java.util.LinkedList;

public class Solution {

ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();

public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {

if(root==null){

return result;

}

LinkedList<TreeNode> queue=new LinkedList<TreeNode>();

queue.offer(root);

int size=queue.size();

while(size>0){

ArrayList<Integer> list=new ArrayList<Integer>();

for(int i=0;i<size;i++){

TreeNode node=queue.poll();

list.add(node.val);

if(node.left!=null){

queue.add(node.left);

}

if(node.right!=null){

queue.add(node.right);

}

result.add(0,list);

size=queue.size();

}

return result;

}

发表于 2017-08-19 15:43:41 回复(0)

Java

pp11

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if (root == null)
            return list;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int size = 0;
        TreeNode temp = null;
        while (!queue.isEmpty()) {
            size = queue.size();
            ArrayList<Integer> tempList = new ArrayList<Integer>();
            for (int i = 0; i < size; ++i) {
                temp = queue.poll();
                tempList.add(temp.val);
                if (temp.left != null)
                    queue.offer(temp.left);
                if (temp.right != null)
                    queue.offer(temp.right);
            }
            list.add(tempList);
        }
        for (int i = 0; i < list.size() / 2; ++i) {
            ArrayList<Integer> tempList = list.get(i);
            list.set(i, list.get(list.size() - 1 - i));
            list.set(list.size() - 1 - i, tempList);
        }
        return list;
    }
}

发表于 2017-08-06 22:28:36 回复(0)

Java

Holiday_12138

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(root == null)
            return res;
        ArrayList<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        q.add(root);
        q.add(null);
        while(!q.isEmpty()) {
            TreeNode r = q.remove();
            if(r != null) {
                s.push(r);
                if(r.right != null)
                    q.add(r.right);
                if(r.left != null)
                    q.add(r.left);
            }
            else {
                if(!q.isEmpty()) {
                    s.push(null);
                	q.add(null);
                }
            }
        }
        while(!s.isEmpty()) {
            TreeNode r = s.pop();
            if(r != null)
                list.add(r.val);
            else {
                res.add(list);
                list = new ArrayList<Integer>();
            }
        }
        if(list.size() > 0)
            res.add(list);
        return res;
    }
}

发表于 2017-06-26 13:51:02 回复(0)

Java

牛妹老公

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();// 用来返回结果集合
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        if(root == null)
            return result;
        list.add(root);        
        while(!list.isEmpty()){
            int count = list.size();
            for(int i=0; i< count;i++){
                TreeNode node = list.remove(0);
                temp.add(node.val);
                if(node.left != null){
                    list.add(node.left);
                }
                if(node.right != null){
                    list.add(node.right);
                }
                if(i == count -1){    
                    result.add(new ArrayList<Integer>(temp));
                    temp.clear();
                }
            }            
        }
        Collections.reverse(result);
        return result;
    }
}

发表于 2017-05-08 21:55:14 回复(0)

Java

ephonzhang

public class BinaryTreeLevelOrderTraversalII {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> oldQueue = new LinkedList<>();
        Queue<TreeNode> newQueue = new LinkedList<>();
        oldQueue.add(root);
        ArrayList<Integer> tempList = new ArrayList<>();

        while (!oldQueue.isEmpty() || !newQueue.isEmpty()) {
            while (!oldQueue.isEmpty()) {
                TreeNode node = oldQueue.peek();
                tempList.add(node.val);
                if (node.left != null) newQueue.add(node.left);
                if (node.right != null) newQueue.add(node.right);
                oldQueue.remove(oldQueue.peek());
            }
            result.add(0, tempList);
            tempList = new ArrayList<>();
            oldQueue.addAll(newQueue);
            newQueue.clear();
        }

        return result;
    }
}

发表于 2017-04-24 20:02:01 回复(0)

Java

城市里的养猫者

public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> wrapList = new LinkedList<List<Integer>>(); if(root == null) return wrapList; queue.offer(root); while(!queue.isEmpty()){
            int levelNum = queue.size(); List<Integer> subList = new LinkedList<Integer>();
            for(int i=0; i<levelNum; i++) { if(queue.peek().left != null) queue.offer(queue.peek().left); if(queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            wrapList.add(0, subList);
        } return wrapList;
    }
}

发表于 2017-03-12 10:52:24 回复(0)

Java

詆調壹點

import java.util.*;
public class Solution {
   public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<>();
		if(root == null) return res;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while ( ! queue.isEmpty()) {
			ArrayList<Integer> list = new ArrayList<>();
			int size = queue.size();
			for (int i = 0; i < size; i ++ ) {
				TreeNode temp = queue.poll();
				list.add(temp.val);
				if(temp.left != null) queue.add(temp.left);
				if(temp.right != null) queue.add(temp.right);
			}
			res.add(0,list);
		}
		return res;
	}
}

发表于 2016-11-01 19:19:27 回复(2)