# Populating Next Right Pointers in Each Node 设置二叉树的next节点

Given a binary tree

```    struct TreeLinkNode {
}
```

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

一次对每个节点进行遍历，若左右子树不为空，则将左子树的next指向右子树，若该节点的next为空，则将右子树的next设置为空(看图分析)

若该节点的next不为空，则指向与该节点同层次中相邻的右侧节点的左子树(看图分析)

这里使用一个队列，将根节点先放入队列，从队列中取出一个节点node，node移除队列，node子树的next节点处理按照上面分析操作。

``` 1 /**
2  * Definition for binary tree with next pointer.
4  *  int val;
5  *  TreeLinkNode *left, *right, *next;
6  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
7  * };
8  */
9 class Solution {
10 public:
12         if(root == NULL)    return;
14
15         root->next = NULL;
16
17         q.push(root);
18
19         while(!q.empty()){
21             q.pop();
22
23             if(node->left != NULL && node->right != NULL){
24                 q.push(node->left);
25                 q.push(node->right);
26
27                 node->left->next = node->right;
28                 if(node->next == NULL)
29                     node->right->next = NULL;
30                 else{
32                     node->right->next = node_next->left;
33                 }
34
35             }
36
37         }
38
39     }
40 };```

## Populating Next Right Pointers in Each Node

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

## 【56】116. Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node Description Submission Solutions Add to List Total Accepted: 118451 Total Submissions: 321021 Difficulty: Medium Contributors: Admin Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLi

## leetcode - Populating Next Right Pointers in Each Node I&amp;II

Populating Next Right Pointers in Each Node I 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 nex

## LeetCode OJ：Populating Next Right Pointers in Each Node II（指出每一个节点的下一个右侧节点II）

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example,Given the following binary tr

## [leetcode] 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, al

## leetcode 117 Populating Next Right Pointers in Each Node II ----- java

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example,Given the following binary tr

## LeetCode[Tree]: Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example, Given the following binary t

## Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example, Given the following binary t

## Populating Next Right Pointers in Each Node II LeetCode

Populating Next Right Pointers in Each Node II Total Accepted: 18934 Total Submissions: 62031My Submissions Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous