LeetCode: Populating Next Right Pointers in Each Node I && II

I

还是……树的递归性质，但是稍微有点绕。由于只能够使用常数的额外空间，也就意味着不能用BFS来遍历树，只能用DFS。
题目给出条件，这棵树一定是满二叉树，因此这个对称性肯定要被利用到。于是自然而然想到，使用两个对称指针对树进行DFS。递归时的操作很简单，就是把左节点的next指针指向右节点，只是递归方式上有点小技巧。我们不仅仅要递归处理左子树与右子树，同时，也要把左子树的所有右侧节点，各自连接到右子树的所有左侧节点上去。这个操作只需要交换递归时传参的次序即可简洁地完成，代码写出来非常漂亮！

II

第二问就有点难度了，此时不再保证满二叉树的条件，因此必须换一种不同的写法。仍然是从树的递归性质入手考虑，我们发现在每一个根节点处的操作，无非就是两步：先设置节点左儿子的next指针，将其指向同一层且在其右侧的，最靠左的节点；然后再设置右儿子的next指针，将其指向同一层且在其右侧的，最靠左的节点。
所以问题的核心就转换为：如何找到对应于左右儿子的，最靠左的节点？显然，如果左右儿子均存在，那么对应于左儿子的最靠左的节点显然就是右儿子本身；但如果只有右儿子或者只有左儿子，那么这个“最靠左节点”的找法一定是一样的！
于是问题进一步转换为，如何寻找对应于右儿子的“最靠左”节点。我们不妨这样考虑：沿着当前根节点的next指针不断向右前进，如果遇到一个可以向下移动一层的机会，那么所移动到的节点必然就是所谓的“最靠左”节点。所以显然在“尝试”向下移动的时候，应该先尝试走left指针，再尝试right指针，这样才能够保证找到的是最靠左的节点。
上述问题都得以解决以后，我们便可以顺利执行完当前节点的操作，于是可以进一步递归子节点。此时我们发现，指针的建立过程其实是自顶向下的——先完成上层，才会继续处理下层。再回到找“最靠左”节点的过程，我们发现这个过程中用到了右半边的转移关系，因此也就意味着先前必须已经递归处理了右子树，才能在此时找到正确的节点。
总而言之，这两道题目确实是非常好的，考察对于树的递归性质的理解的题目。

代码

第一问

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if ( root == NULL ) return;
        DFS(root->left, root->right);
    }
    void DFS( TreeLinkNode *root1, TreeLinkNode *root2 ) {
        if ( root1 == NULL || root2 == NULL ) return;
        root1->next = root2;
        DFS(root1->left, root1->right);
        DFS(root2->left, root2->right);
        DFS(root1->right, root2->left);
    }
};

第二问

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if ( root == NULL ) return;
        TreeLinkNode *p = root->next;
        while ( p != NULL ) {
            if ( p->left != NULL ) {
                p = p->left;
                break;
            } else if ( p->right != NULL ) {
                p = p->right;
                break;
            }
            p = p->next;
        }
        if ( NULL != root->right ) root->right->next = p;
        if ( NULL != root->left ) root->left->next = root->right == NULL ? p : root->right;
        connect(root->right);
        connect(root->left);
    }
};