二叉树的层序遍历 II
题目链接
二叉树的层序遍历 II
题目描述
注意点
- 树中节点数目在范围 [0, 2000] 内
- -1000 <= Node.val <= 1000
解答思路
- 根据队列先进先出的特点层序遍历所有的节点（从左到右），又因为需要自底向上的输出层序遍历的结果，所以可以将每一次遍历的结果存储到栈中，根据栈先进后出的特点将结果输出
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Deque<List<Integer>> stack = new ArrayDeque<>();Deque<TreeNode> queue = new ArrayDeque<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> list = new ArrayList<>(size);stack.push(list);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);}}while (!stack.isEmpty()) {res.add(stack.pop());}return res;}
}
关键点
- 栈和队列的特点及使用