正文
LeetCode OJ：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
这题首先想到的当然是用bfs来做，但是题目只允许使用常数量的额外空间，用queue肯定是无法实现的，那么可以采取先序遍历的方式，由于是完全二叉树，所以有左孩子那么就一定也有右孩子了，所以递归的时候注意这点就可以了。下面是代码：
class Solution {
public:
void connect(TreeLinkNode *root) {
preorderTranversal(root);
}
void preorderTranversal(TreeLinkNode *root)
{
if(!root || !root->left) return;
root->left->next = root->right;
if(root->next)
root->right->next = root->next->left;//这一步的连接应该注意一下
preorderTranversal(root->left);
preorderTranversal(root->right);
}
};
当然这题也可以使用非递归的方法来实现，非递归方法代码如下所示：
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == NULL) return ;
while(root->left){
TreeLinkNode * tmpRoot = root;
tmpRoot->left->next = tmpRoot->right;
while(tmpRoot->next){
tmpRoot->right->next = tmpRoot->next->left;
tmpRoot = tmpRoot->next;
if(tmpRoot->left)
tmpRoot->left->next = tmpRoot->right;
}
root = root->left;
}
}
};
