116. Populating Next Right Pointers in Each Node

# Medium

Two methods:

1. Recursive (由于是完全二叉树，所以若节点的左子结点存在的话，其右子节点必定存在，所以左子结点的 next 指针可以直接指向其右子节点，对于其右子节点的处理方法是，判断其父节点的 next 是否为空，若不为空，则指向其 next 指针指向的节点的左子结点，若为空则指向 NULL)

2. No-recursive + BFS(use queue)

Python (2)

# 方法二，非递归
# 我写的
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        # edge case
        if root == None:
            return None
        
        # regular case
        queue = []
        queue.append(root)
        while len(queue) != 0:
            n = len(queue)
            tmp = queue.pop(0)
            while n >= 1:
                if tmp.left != None:
                    queue.append(tmp.left)
                    queue.append(tmp.right)
                    
                if n == 1:
                    tmp.next = None
                else:
                    right = queue.pop(0)
                    tmp.next = right
                    tmp = right
                n -= 1
                
        return root

C++ (1)

// 方法一，递归的方法，找父节点？
// 不需要，只判断父节点，通过父节点给子节点加上next
// 不是我写的
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        if (root->left) root->left->next = root->right;
        if (root->right) root->right->next = root->next? root->next->left : NULL;
        connect(root->left);
        connect(root->right);
        return root;
    }
};

非递归的方法，n 为tree的高度，时间复杂度为 $O(2^n - 1)$ ，因为需要遍历所有的节点，空间复杂度为叶子节点的个数 $O(2^{n-1})$