PopulatingNextRightPointersInEachNode [source code]

public class PopulatingNextRightPointersInEachNode {
static
/******************************************************************************/
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode cur = root;
        while (cur != null) {
            TreeLinkNode list_cur = cur, list_prev = null;
            while (list_cur != null) {
                if (list_cur.left == null)
                    break;
                list_cur.left.next = list_cur.right;
                if (list_prev != null)
                    list_prev.right.next = list_cur.left;
                list_prev = list_cur;
                list_cur = list_cur.next;
            }
            cur = cur.left;
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PopulatingNextRightPointersInEachNode.Solution tester = new PopulatingNextRightPointersInEachNode.Solution();
    }
}

constant extra space是什么意思, 不允许用queue吗? tag又写一个DFS, 拿意思是recursion Stack就无所谓?

这题用BFS确实太trivial了;

还是吃不准这里的空间要求到底是什么意思, 然后估计discuss肯定有人讨论, 就去看了一下:

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37500/Hint-for-O(1)-space

If you don’t want a solution for O(1) space but just a hint, here it is: you need to make use of the next links that you’re creating.

然后大概思考了一下, 好像就有点思路了;

最后调了几个小bug之后就AC了, 速度是1ms (30%).

最后实际上还是一个BFS的手段, 但是这里的这个next指针实际上就是让你思考怎么不用queue来做一个BFS;

没有editorial;

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37472/A-simple-accepted-solution

void connect(TreeLinkNode *root) {  
    if (root == NULL) return;  
    TreeLinkNode *pre = root;  
    TreeLinkNode *cur = NULL;  
    while(pre->left) {  
        cur = pre;  
        while(cur) {  
            cur->left->next = cur->right;  
            if(cur->next) cur->right->next = cur->next->left;  
            cur = cur->next;  
        }  
        pre = pre->left;  
    }  
}

you need two additional pointer.

大概思路是一样的, 在左边大梁用一个指针来走tree, 然后每一个level单独用两个指针来跑level; 不同的是他对一个level的操作是在当前的level直接用cur.next来完成, 而不是像我这样用一个prev来完成跨subtree的连接;

Sleet solution! A more intuitive way might be:
(1) Loop through level 0 to level n - 2; (2) Traverse this level and connect children. This takes 1ms:

public void connect(TreeLinkNode root) {  
    while(root != null && root.left != null) {  
        TreeLinkNode cur = root;  
        while(cur != null) {  
            cur.left.next = cur.right;  
            cur.right.next = cur.next == null ? null : cur.next.left;  
            cur = cur.next;  
        }  
        root = root.left;  
    }  
}

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37461/Java-solution-with-O(1)-memory+-O(n)-time

public class Solution {  
    public void connect(TreeLinkNode root) {  
        TreeLinkNode level_start=root;  
        while(level_start!=null){  
            TreeLinkNode cur=level_start;  
            while(cur!=null){  
                if(cur.left!=null) cur.left.next=cur.right;  
                if(cur.right!=null && cur.next!=null) cur.right.next=cur.next.left;  

                cur=cur.next;  
            }  
            level_start=level_start.left;  
        }  
    }  
}

这个就跟我的思路其实非常类似了;

according to the Note of this question,
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).
The method could return when cur.left == null

我就是这样做的;

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37473/My-recursive-solution(Java)

public void connect(TreeLinkNode root) {  
    if(root == null)  
        return;  

    if(root.left != null){  
        root.left.next = root.right;  
        if(root.next != null)  
            root.right.next = root.next.left;  
    }  

    connect(root.left);  
    connect(root.right);  
}

很多这样的recursion的做法, 但是实际上这种做法对于这题肯定是不对的;

This is actually O(1) stack space in most languages as the compilers optimize to reuse the recursive stack. You guys need to look at what is called Tail Recursion. Unfortunately, the Java compiler does not optimize this way.

依赖优化毕竟不是最solid的思路;

@anat By extra space usually it refers to not using any additional data Structure. Though you can clarify this with the Interviewer

问是最保险的;

submission最优解好像就是上面这个recursion的做法; 看淡点;

Problem Description

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

Difficulty:Medium
Total Accepted:163.6K
Total Submissions:443.2K
Contributor:LeetCode
Companies
microsoft
Related Topics
treedepth-first search
Similar Questions
Populating Next Right Pointers in Each Node IIBinary Tree Right Side View