116. Populating Next Right Pointers in Each Node

最后更新

三刷

看起来是level order traversal，但是直接硬来的话，doing this iteratively requires O(n) space for a Stack; while recursively doing this requires O(n) as well for Memory Stack...

正规做法是遍历某一次层的时候链接他下面那一层的next pointer。

利用了第一行ROOT只有一个NODE，通过这个链接下一层的next pointer；然后进入下一层，利用刚刚做好的next pointer遍历这一层，同事链接下一层的next pointers...

Time: O(N) 遍历...
Space: O(1) 几个temp pointer..

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode nextLvlEntry = new TreeLinkNode(0);
        
        while (root != null) {
            nextLvlEntry.next = root.left;
            TreeLinkNode temp = nextLvlEntry;
            for (; root != null; root = root.next) {
                if (root.left != null) {
                    temp.next = root.left;
                    temp = temp.next;
                }
                if (root.right != null) {
                    temp.next = root.right;
                    temp = temp.next;
                }
            }
            root = nextLvlEntry.next;
        }
    }
}

一刷

其实就是NODE增加一个POINTER，指向它右边的NODE。

有2个信息很关键，1个是初始化是NULL，所以不用手动添加NULL；另1个是树是完整的，省了很多麻烦的判断。

思路就是对于一个点：

左节点链接右节点
左节点的每一个最右节点链接右节点的每一个最左节点

然后下一层。。

public class Solution {
    public void connect(TreeLinkNode root) 
    {
        if(root == null) return;
        if(root.left == null) return;
        else
        {
            
            TreeLinkNode L = root.left;
            TreeLinkNode R = root.right;
            while(L != null)
            {
                L.next = R;
                L = L.right;
                R = R.left;
            }
            
            connect(root.left);
            connect(root.right);
        }
        
    }
}

忘了一刷怎么做的，二刷做完一看和一刷一样。

二刷一开始想的是BFS，用一个PREV记录上一个NODE，从QUEUE里POLL出一个新的NODE，就用PREV链接。

然后加一个判断，判断PREV是不是上一层的最后一个，是的话就不链接了。

但是这样要用Queue，题目要求constant extra space.

二刷。

回头看发现一刷的做法不对，一刷用的recursion，不是constant space.

要去添加右指针，看起来就是level order traversal的顺序指针。如果不是 constant，直接bfs就行了。

我们BFS的时候，或者说level order traversal的时候，QUEUE里存的是下一层的信息(可以通过计数来确定哪些是下一层的)。

这里可以用一个额外指针记住下一层的开始，当前层的时候顺便把下一层的NEXT指针弄好，这样比那里下一层直接靠next就可以了。

上段所说的“弄好”其实就是，左子 =》右子，右子 =》兄弟的左子，兄弟可以通过 =》来获取。

Time : O(n)
Spalce : O(1)

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        
        TreeLinkNode temp = root;
        TreeLinkNode head = null;
        
        while (temp.left != null) {
            head = temp.left;
            while (temp != null) {
                temp.left.next = temp.right;
                
                if (temp.next == null) {
                    temp.right.next = null;
                } else {
                    temp.right.next = temp.next.left;
                }
                
                temp = temp.next;
            }
            
            temp = head;
        }
    }
}

anothe way from discussion board:

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode temp;
        while (root != null) {
            TreeLinkNode dummy = new TreeLinkNode(0);
            temp = dummy;
            for ( ; root != null; root = root.next) {
                if (root.left != null) {
                    temp.next = root.left;
                    temp = temp.next;
                }
                if (root.right != null) {
                    temp.next = root.right;
                    temp = temp.next;
                }
            }
            root = dummy.next;
        }
    }
}