送分题，就当热手了。
迭代的写法和 CLRS 的伪代码一模一样。
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root != null) queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
rst.add(list);
}
return rst;
}
}
这题的递归写法挺有意思的。
递归写法本质上是对 binary tree 做了一个 pre-order dfs.
对于同一个 level，左面的节点一定比右面节点先 add.
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
dfs(rst, root, 0);
return rst;
}
private void dfs(List<List<Integer>> rst, TreeNode root, int level){
if(root == null) return;
if(level >= rst.size()){
rst.add(new ArrayList<Integer>());
}
rst.get(level).add(root.val);
dfs(rst, root.left, level + 1);
dfs(rst, root.right, level + 1);
}
}
写法一样，最后 reverse 一下就好了。
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
dfs(rst, root, 0);
Collections.reverse(rst);
return rst;
}
private void dfs(List<List<Integer>> rst, TreeNode root, int level){
if(root == null) return;
if(level >= rst.size()){
rst.add(new ArrayList<Integer>());
}
rst.get(level).add(root.val);
dfs(rst, root.left, level + 1);
dfs(rst, root.right, level + 1);
}
}
挺 trivial 的问题。
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
boolean reverse = false;
if(root != null) queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<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.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
if(reverse) Collections.reverse(list);
rst.add(list);
reverse = !reverse;
}
return rst;
}
}
Level order 的写法非常的 trivial，不过这题规定不许手动建任何额外空间（不许存level或者用迭代写，虽然递归也用空间）
考虑到这题给定 perfect tree，不需要考虑中间有拐弯或者空位的问题，递归解决的思路就是用一个 helper 函数传入当前的两个节点（为上一个节点的 left/right child）
迭代依次连接左节点右侧的 path 与 右节点左侧的 path
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null) return;
if(root.left == null && root.right == null) return;
helper(root.left, root.right);
}
private void helper(TreeLinkNode p, TreeLinkNode q){
if(p == null && q == null) return;
if(p == null || q == null) return;
p.next = q;
TreeLinkNode l = p;
TreeLinkNode r = q;
while(q.right != null && q.left != null){
p = p.right;
q = q.left;
p.next = q;
}
helper(l.left, l.right);
helper(r.left, r.right);
}
}
真正的 O(1) 空间是用固定数量的指针进行迭代循环。
这种写法是真正的 level order 添加，利用了上一层完成之后的 next 指针手动做了 level order 遍历。
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null) return;
TreeLinkNode cur = root;
TreeLinkNode leftMost = null;
while(cur.left != null){
leftMost = cur.left;
while(cur != null){
cur.left.next = cur.right;
if(cur.next == null){
cur.right.next = null;
} else {
cur.right.next = cur.next.left;
}
cur = cur.next;
}
cur = leftMost;
}
}
}
在参考了下一题 follow up 的写法之后，这类问题的通解：
public class Solution {
public void connect(TreeLinkNode root) {
while(root != null){
TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode cur = dummy;
for( ; root != null; root = root.next){
if(root.left != null){
cur.next = root.left;
cur = cur.next;
}
if(root.right != null){
cur.next = root.right;
cur = cur.next;
}
}
root = dummy.next;
}
}
}
搞了半天一直处于一个追着各种 test case 改 Bug 的阶段，而且要改的细节越来越多。。。写题如果发现自己陷入了这个阶段，还是果断换思路把。
这题的迭代思路和上一题一样，充分利用好上一层已经是连好的next指针来做 level order. 然而有几个很烦的地方需要处理:
中间有空缺节点的话，怎么让上层找到“下一个”正确的节点
如果某一层最左边有空缺的话，如何在进入下一层的时候找到正确的起点
这个解法的思路非常简洁优美。因为对题本质的理解更进一步了：
我们要做的其实是 level order 建一个 LinkedList 出来。
于是这题几个最烦人的细节处理，都可以靠 dummy node 解决。
这题也是继 word ladder 之后另一个不同的 for 循环写法，字符和链表都很适合用 for loop 实现遍历。
public class Solution {
public void connect(TreeLinkNode root) {
while(root != null){
TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode cur = dummy;
for( ; root != null; root = root.next){
if(root.left != null){
cur.next = root.left;
cur = cur.next;
}
if(root.right != null){
cur.next = root.right;
cur = cur.next;
}
}
root = dummy.next;
}
}
}
这题本质上还是在做 level order 遍历，因为最终结果上 node 是按层数依次添加的。
于是回想下递归版的 level order traversal，我们做 dfs pre-order
【中，左，右】 的顺序可以保证上面一层的节点永远会比下一层的先建立；
同时对于每一层，我们一定会先发现最左面的节点，而后才是右面依次发现。
把这个性质根据题意改一下，我们就有了
【中，右，左】 首先保证了 level order，因为对于所有子树，中节点要比左右子树先执行；
同时因为子树顺序是 【右，左】，同一 level 的节点一定是从右到左被发现的。
因此只要注意判断条件，只把第一次发现的元素添加进去，然后做改变顺序版 preorder traversal 就好了。
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
helper(root, list, 0);
return list;
}
private void helper(TreeNode root, List<Integer> list, int level){
if(root == null) return;
if(level == list.size()) list.add(root.val);
helper(root.right, list, level + 1);
helper(root.left, list, level + 1);
}
}