LeetCode Populating Next Right Pointers in Each Node (技巧)

题意:

  给一棵满二叉树,要求将每层的节点从左到右用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代码

  

上一篇:vue 项目使用 webpack 构建自动获取电脑ip地址


下一篇:bitnami_redmine3.3.0-1 问题及备份恢复