You are given a **perfect binary tree** where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1 2 3 4 5 6 |
struct Node { int val; Node *left; Node *right; Node *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`

.

**Example:**

Input:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}Output:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}Explanation:Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

**Note:**

- You may only use constant extra space.
- Recursive approach is fine, implicit stack space does not count as extra space for this problem.

**Solution: Recursion**

Do a preorder traversal:

1. return if self is empty or leaf

2. self.left->next = self.right

3. if self.next: self.right.next = self.next.left

Time complexity: O(n)

Space complexity: O(log(n)) since it’s a perfect tree

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: void connect(TreeLinkNode *root) { if (!root) return; if (!root->left || !root->right) return; root->left->next = root->right; if (root->next) root->right->next = root->next->left; connect(root->left); connect(root->right); } }; |

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。

如果您喜欢这篇文章／视频，欢迎您捐赠花花。

If you like my articles / videos, donations are welcome.

## Be First to Comment