题意:
给一棵满二叉树,要求将每层的节点从左到右用next指针连起来,层尾指向NULL即可。
思路:
可以递归也可以迭代。需要观察到next的左孩子恰好就是本节点的右孩子的next啦。
(1)递归:这个更快。
/**
* 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 DFS(TreeLinkNode* root,TreeLinkNode* t)
{
if(root->next==NULL && t!=NULL) root->next=t->left;
if(root->left)
{
root->left->next=root->right;
DFS(root->left, NULL);
DFS(root->right,root->next);
}
}
void connect(TreeLinkNode *root) {
if(root) DFS(root,NULL);
}
};
AC代码
(2)递归:这个简洁。
/**
* 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 && root->left)
{
root->left->next=root->right;
if(root->next)
root->right->next=root->next->left;
connect(root->left);
connect(root->right);
} }
};
AC代码
(3)迭代:这个更吊。
/**
* 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) {
while(root&&root->left)
{
TreeLinkNode *p=root;
while(p)
{
p->left->next=p->right;
if(p->next)
p->right->next=p->next->left;
p=p->next;
}
root=root->left;
}
}
};
AC代码