【107-Binary Tree Level Order Traversal II（二叉树层序遍历II）】
【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】
原题
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 7return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]题目大意
给定一棵二叉树自底向下进行层序遍历。
解题思路
对树进行层序遍历，每层的结果放在结果链表的头部。
代码实现
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}算法实现类
import java.util.*;
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> list = new LinkedList<>();
if (root == null) {
return list;
}
Deque<TreeNode> cur = new LinkedList<>();
Deque<TreeNode> nxt = new LinkedList<>();
Deque<TreeNode> exc = new LinkedList<>();
TreeNode tmp;
cur.add(root);
while (!cur.isEmpty()) {
List<Integer> layout = new ArrayList<>();
while (!cur.isEmpty()) {
tmp = cur.remove();
if (tmp.left != null) {
nxt.add(tmp.left);
}
if (tmp.right != null) {
nxt.add(tmp.right);
}
layout.add(tmp.val);
}
exc = cur;
cur = nxt;
nxt = exc;
list.add(0, layout);
}
return list;
}
}评測结果
点击图片，鼠标不释放，拖动一段位置。释放后在新的窗体中查看完整图片。
