【LeetCode】Populating Next Right Pointers in Each Node II典型异常示例与分析

【LeetCode】Populating Next Right Pointers in Each Node II典型错误示例与分析

博客沉寂了小半年，现在放了假终于又闲下来了，从今天开始每天要继续做题，争取每天更新一篇博文！

这道题我采用的办法没有任何技术含量，沿用问题一中的思路采用深度优先搜寻，对每个节点分别递归左右子树，但是提交了几次都没有通过，最后一次提交的代码如下

/**
 * 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函数中，为了方便观察我画了一个树图辅助分析。