【LSP】LeetCode (23):二叉树的层次遍历 II
http://cdn.u1.huluxia.com/g4/M01/5A/80/rBAAdl9ulvGAU4ZMAACt4WdlvYs091.jpg
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 ,
3
/ \
920
/\
15 7
返回其自底向上的层次遍历为:
[
,
,
]
解题思路
看到这道题,如果还有不会做的同学,可能需要受到马桶搋子的教育。
这道题和昨天的那道题基本上是同一道题,昨天的那道题是一个顺序遍历,这道题是一个逆序遍历。
顺序遍历使用的是队列的结构,逆序遍历能想到啥?
当然是栈啊,队列是先进先出的数据结构,而栈是一个先进后出的数据结构。
在使用栈的时候只要按照循序把元素一个一个放进去放好,最后再拿出来直接就是一个逆序的结构,完全不需要多余的处理的好么。
解法一:使用栈
这个解法就是把昨天的代码上加上一个栈,在每次循环的时候把元素放到栈里,最后迭代一次栈,将栈中的元素输出后返回。
// 顺序思维操作 耗时 2ms
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null) return new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 新增一个数据结构,栈
Stack<List<Integer>> stack = new Stack<>();
// 外层循环,每次循环都是一层
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
// 循环这一层的所有节点
while (size > 0) {
TreeNode node = queue.poll();
// 将这一层的所有节点放到 list 中
list.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
size--;
}
// 将列表当道栈中
stack.push(list);
}
// 将栈中数据取出来放到列表中
while (!stack.isEmpty()) {
result.add(stack.pop());
}
return result;
}
这段代码稍微有点长,不过很好理解,完全的顺序思维。
不知道你们发现没有,越长的代码越容易看懂,越短的代码理解起来越费劲,就比如昨天的那个递归的方法,总共就两行,想看懂还是有点难度的。
http://cdn.u1.huluxia.com/g4/M01/5A/80/rBAAdl9ulvKAFzGqAABBnMZgoZw857.png
页:
[1]