Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

 

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

Naive Way:这次多了一个不满秩的条件，很明显的意图是要看能否通过修改第一次的代码得到。

第一次的代码：

public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        TreeLinkNode leftMost = root;
        TreeLinkNode node = null;
        while(leftMost.right!=null && leftMost.left!=null){
            node = leftMost;
            leftMost = node.left;
            do{
                node.left.next = node.right;
                node.right.next = node.next==null?null:node.next.left;
                node = node.next;
            }while(node!=null);
        }
    }

我想基本结构应该是不变，但是现在左子节点和右子节点都可能不存在。分析一下不存在的时候该怎么办：

1.如果左子节点不存在，最左边的节点就应该是右节点。

2.如果右子节点不存在，next该指向的是父节点的next节点的左子节点。

很棒，这两点是相互作用的.对于找最左子节点和右节点分别写了对应函数，发现二者仅一处不同。

private TreeLinkNode searchLeft(TreeLinkNode node){
        if(node==null)
            return null;
        if(node.left!=null)
            return node.left;
        if(node.right!=null)
            return node.right;
        return searchLeft(node.next);
    }

private TreeLinkNode searchRight(TreeLinkNode node){
        if(node==null)
            return null;
        if(node.right!=null)
            return node.right;
        return searchLeft(node.next);
    }

替换相应部分的结果为：

（这里结束条件需要略作改动，因为不能再用是否满秩作为判断条件。后来想想，应该第一个也这样写的） 

public void connect(TreeLinkNode root) {

       if(root==null)

           return;

       TreeLinkNode leftMost = root;

       TreeLinkNode node = null;

       while(leftMost!=null){

           node = leftMost;

           leftMost = searchLeft(node);

           do{
              if(node.left!=null)

                   node.left.next = searchRight(node);

               if(node.right!=null)

                   node.right.next = searchLeft(node.next);

               node = node.next;

           }while(node!=null);

       }

   } 

Improved Way: 这样是否就已经可以了呢。我在discuss中看到一个很有意思的想法。有个人先把搜友节点的next节点指向父节点，然后展开BFS把next pointer指向下一个。感觉和我的思路是一样的，都是要先把上一层的next连好，记下下一层最左边的，然后通过上一层的next找同层的兄弟节点。但是把next指向父节点就有了无限可能性，因为可以no extra space从下往上遍历节点了。

以下代码是leetcode用户 pavan.singitham的。

public class Solution {
public void connect(TreeLinkNode root) {
    if(root == null) {
        return;
    }
    root.next = null;
    pointChildrenToParents(root);
    rotateNextClockwise(root);
}

// point each child's next pointer to the parent
private void pointChildrenToParents(TreeLinkNode root) {
    if(root == null) {
        return;
    }
    if(root.left != null) {
        root.left.next = root;
        pointChildrenToParents(root.left);
    }
    if(root.right != null) {
        root.right.next = root;
        pointChildrenToParents(root.right);
    }
}

// now update the next pointer 1-level at a time to point to the next node in that level
private void rotateNextClockwise(TreeLinkNode root) {
    if(root == null) {
        return;
    }

    TreeLinkNode firstNodeInNextLevel = null; // save first node in next level for bfs
    while(root != null) {
        if(firstNodeInNextLevel == null) {
            firstNodeInNextLevel = (root.left != null)? root.left : root.right;
        }
        if(root.right != null) {
            if(root.left != null) {
                root.left.next = root.right;
            }
            root.right.next = findNextChild(root.next);
            root = (root.right.next != null) ? root.right.next.next: null;
        }
        else if(root.left != null) {
            root.left.next = findNextChild(root.next);
            root = (root.left.next != null) ? root.left.next.next: null;
        }
        else {
            root = root.next;
        }
    }

    rotateNextClockwise(firstNodeInNextLevel);
}

// traverse next chain till we find a child for current level
private TreeLinkNode findNextChild(TreeLinkNode root) {
    for(TreeLinkNode tmp = root; tmp != null; tmp = tmp.next) {
        if(tmp.left != null) {
            return tmp.left;
        }
        else if(tmp.right != null) {
            return tmp.right;
        }
    }
    return null;
} 

} 

看到一个更好的代码，思路是一样的，带式代码质量好很多。来自leetcode的 davidtan1890用户。

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;
        }
    }