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:
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.
定义Node可指向其左子树、右子树和下一个结点,下一个结点就是水平方向上的其右边的结点。当右边没有结点时,其next值为NULL。
本题给出完全二叉树,所有结点的next初始值为NULL,给各节点的next赋予正确的值。
提醒:使用固定大小的额外空间
递归方法很好,隐式堆栈空间不算作此问题的额外空间。
要求右子树根结点的next就要有根结点的next,因此要从上到下进行操作。
方法一:使用两个迭代器,第一个迭代器沿左支从上到下遍历,另一个迭代器在此基础上从左到右对结点进行next赋值操作。
代码如下:
class Solution { public: Node* connect(Node* root) { if(!root)return NULL; Node* cur=root; while(cur->left){ Node *p=cur; while(p){ p->left->next=p->right; if(p->next){ p->right->next=p->next->left; } p=p->next; } cur=cur->left; } return root; } };
方法二:递归法。求next的值的方法和方法一相同,只是这里用递归的方法代替了从上到下的层序遍历。
代码如下:
class Solution { public: Node* connect(Node* root) { if(!root)return NULL; if(root->left){ root->left->next=root->right; if(root->next){ root->right->next=root->next->left; } } connect(root->left); connect(root->right); return root; } };
方法三:使用堆栈代替递归操作。将每一层的结点从左向右依次放如queue中,然后从头依次取出结点,同时将下一层的结点放进去。
代码如下:
class Solution { public: Node* connect(Node* root) { if(!root)return NULL; queue<Node*> q; q.push(root); while(!q.empty()){ int len=q.size(); while(len){ Node* cur=q.front(); q.pop(); if(--len)cur->next=q.front(); if(cur->left)q.push(cur->left); if(cur->right)q.push(cur->right); } } return root; } };