Leetcode 116 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

注意： 递归的方法不是 constant space, 会 O logN 的calling deep， 所以要想其他办法做到遍历全部节点： 

一个p 指针横着走，就会利用之前已经保存的信息，然后有个指针一直指向最左边

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

递归的写法，虽然对这题是不可以的，但递归的思路要清楚： 

1. 先判断返回或是异常条件
2. 做一些逻辑上的判断
3. 基本是 左右子树的判断

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