leetcode: Populating Next Right Pointers in Each Node

问题描述：

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

 

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

 

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

 

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

原问题链接：https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

 

问题分析

　　这个问题的要求相对来说比较严格，因为要求有常量个的额外空间来解决问题，因此这里就不能直接用树的层次序遍历的办法。因为按照那个办法，我们可以得到一层的节点，然后再把下一层的放到另外一个列表中。因此，我们需要考虑一下利用问题里提供的其他条件。

　　问题中还有几个额外的条件，就是我们可以假设整棵树是完美二叉树。也就是说，除了叶节点，其余每个节点都有两个子节点。 如果我们需要层次序的去遍历这颗二叉树的话，肯定首先要从根节点开始。它作为当前层的节点。而要能够继续遍历下一层，我们需要在当前节点的下一层节点，也就是当前层第一个节点的左子节点作为下一层的节点。这样我们才能遍历完一层后继续遍历下一层。

　　在上述的这个循环里，我们退出的条件就是当前节点的左子节点为空。这个时候意味着我们已经到了叶节点这一层了。

　　而在每一层的循环中，我们要将当前节点的左子节点的next指向它的右子节点。同时还有一个值得注意的地方，就是当它还有下一个节点，也就是它的next引用指向的节点不为空的情况下，它的右子节点的next要指向它的next元素的左子节点。这样一直到它的next为空。

　　结合上述的讨论，我们可以得到如下的代码：

 

/**
 * 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;
        TreeLinkNode curLevel = root, nextLevel = root.left;
        while(curLevel.left != null) {
            curLevel.left.next = curLevel.right;
            if(curLevel.next != null) {
                curLevel.right.next = curLevel.next.left;
                curLevel = curLevel.next;
            } else {
                curLevel.right.next = null;
                curLevel = nextLevel;
                nextLevel = curLevel.left;
            }
        }
    }
}

　　这里问题的思路没有直接硬套树的层次遍历解决的套路，因为我们可以利用一些额外的条件，可以让整个问题的解法空间消耗更低。 而这里问题能够得到顺利解决的关键是任何一个非叶节点的元素都有左右两个子节点。