博客沉寂了小半年，现在放了假终于又闲下来了，从今天开始每天要继续做题，争取每天更新一篇博文！
这道题我采用的办法没有任何技术含量，沿用问题一中的思路采用深度优先搜寻，对每个节点分别递归左右子树，但是提交了几次都没有通过，最后一次提交的代码如下
/** * Definition for binary tree with next pointer. * public class TreeLinkNode { *int val; *TreeLinkNode left, right, next; *TreeLinkNode(int x) { val = x; } * } */public class Solution {public void connect(TreeLinkNode root) {if (root==null) return;root.next=null;selfconnect(root);}public void selfconnect(TreeLinkNode node){if (node==null) return;if (node.left!=null&&node.right!=null){node.left.next=node.right;node.right.next=findNextNode(node);}else if (node.left==null&&node.right!=null){node.right.next=findNextNode(node);}else if (node.left!=null&&node.right==null){node.left.next=findNextNode(node);}selfconnect(node.left);selfconnect(node.right);}public TreeLinkNode findNextNode(TreeLinkNode parent){while (parent.next!=null){if (parent.next.left!=null) return parent.next.left;else if (parent.next.right!=null) return parent.next.right;else parent = parent.next;}return null;}}而给出的结果是WA：Input:{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}Output:{2,#,1,3,#,0,7,9,1,#,2,1,0,#,7,#}Expected:{2,#,1,3,#,0,7,9,1,#,2,1,0,8,8,#,7,#}观察结果可以发现，，我的程序的前部分输出没有问题，后半部分有两个节点8被漏掉了，而这个问题应该出在findNextNode函数中，为了方便观察我画了一个树图辅助分析。
问题出在第四行的元素0上，按照程序思路去找下一个节点时，首先判断其父亲节点有没有next，如果有则按顺序判断其有没有左孩子或右孩子，都没有则去找它的next，直到找到一个非空元素或next为空。
但是！！！问题来了！！！。。。
由于我们是深度优先，访问顺序是2-1-0-2-7-1-0-7…即前序遍历，节点9并没有被访问，于是它的next还并没有指向节点1，这就造成了找节点0的next时无法正确找到1的左孩子了。由此可见，针对此问题，深度优先是行不通的！！那么怎么办？
答案是层次遍历。
discuss中的best answer，确实很简单，两个循环，大循环遍历每一层，小循环遍历一层中的各个节点。
public class Solution {public void connect(TreeLinkNode root) {while(root != null){TreeLinkNode tempChild = new TreeLinkNode(0);TreeLinkNode currentChild = tempChild;while(root!=null){if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}root = root.next;}root = tempChild.next;}}}
经受雨，面对另一个轮回。
