LeetCode 树

1.populating-next-right-pointers-in-each-node-ii

题目描述：填充所有节点的next指针，指向它右兄弟节点。如果没有右兄弟节点，则应该将next指针设置为NULL。初始时，所有的next指针都为NULL
注意：你只能使用常量级的额外内存空间；可以假设给出的二叉树是一个完美的二叉树(即，所有叶子节点都位于同一层，而且每个父节点都有两个孩子节点)。
解题思路：我的解题思路就是我永远也忘不掉的（田老师）层次遍历思路父结点出队，子节点依次入队，只需要根据完美二叉树性质，找准每一层最后一个结点即可。
不管方法是不是最简洁的，本题写好代码一遍过令人开熏！

2.populating-next-right-pointers-in-each-node-ii

题目描述：
继续思考"Populating Next Right Pointers in Each Node".这道题
如果给定的树可以是任意的二叉树呢?你之前的给出的算法还有效吗?
注意：你只能使用常量的额外内存空间
解题思路：我的解题思路就是在上一道题层次遍历结点依次入队的基础上，再加入一个临界隔板结点也让他入队，标志着这一层结束。

import java.util.Queue;
import java.util.LinkedList;

public class Solution {
    public void connect(TreeLinkNode root) {
        //层序遍历，pre记录上一个兄弟，层切换时断链
        Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
        if(root==null)    return ;
        queue.add(root);
        TreeLinkNode pre = root;
        TreeLinkNode tail = new TreeLinkNode(-65535); //分层隔断点
        queue.add(tail);
        while(!queue.isEmpty() && pre!=tail){
            TreeLinkNode node = queue.poll();
            if(pre!=node){
                pre.next = node;
                pre = pre.next;
            }
            if(node.left!=null)   //左孩子入队
                queue.add(node.left);
            if(node.right!=null){ //右孩子入队
                queue.add(node.right);
            }
            if(queue.peek().val==-65535){//当前点是层尾
                node.next = null;
                tail = queue.poll();
                queue.add(tail);
                pre = queue.peek();    //下一层头
            }
        }
    }
}

层次遍历我田老师当时讲的思路在我脑海中真的是根深蒂固，以至于形成思维定式，我才发现思维被固化也是一件很难受的事，于是我决定去强行找2种层次遍历的其他方法。也看看这道题的其他解法。