# 116 Populating Next Right Pointers in Each Node

## 116. Populating Next Right Pointers in Each Node

## 1. Question

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
```

## 2. Implementation

**(1) Recursion**

```java
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }

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

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

**(2) Iteration**

```java
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }

        TreeLinkNode curNode = root;
        TreeLinkNode leftMostNode = null;

        while (curNode.left != null) {
            leftMostNode = curNode.left;
            while (curNode != null) {
                curNode.left.next = curNode.right;
                curNode.right.next = curNode.next == null ? null : curNode.next.left;
                curNode = curNode.next;
            }
            curNode = leftMostNode;
        }
    }
}
```

## 3. Time & Space Complexity

Recursion: 时间复杂度: O(n), 空间复杂度: O(h)

Iteration: 时间复杂度: O(n), 空间复杂度: O(1)