leetcode_117 填充每个节点的下一个右侧节点指针 II

1. 题意

在一颗树的同层之间用指针把他们链接起来。

填充每个节点的下一个右侧节点指针 II

2. 题解

2.1 BFS

用一个变量记录下同层最右侧的节点，当遍历到时更新下一层的最右侧节点即可。

class Solution {
public:Node* connect(Node* root) {Node *righMost = root;queue<Node *> q;if (root)q.push(root);while (!q.empty()) {Node *cur = q.front();q.pop();if ( cur -> left) q.push(cur->left);if ( cur->right )q.push(cur->right);if (cur == righMost) {righMost = q.back();}else {cur->next = q.front();}}return root;}
};

2.2 BFS+空间优化

在将下一层的节点放入队列时，其实就可以将他们链接起来了。从而省去了队列的空间，此时保存下每一层的最开始的节点就可以了。

class Solution {
public:void handle(Node *&pre, Node *&nextStart,Node *rt) {if (nullptr == rt) return ;if (!pre) {nextStart = rt;}else {pre->next = rt;}pre = rt;}Node* connect(Node* root) {Node *righMost = root;Node *start = root;Node *nextStart = nullptr;Node *pre = nullptr;for ( ;start; start = nextStart) {nextStart = nullptr;pre = nullptr;for ( ;start;start = start->next) {handle(pre, nextStart, start->left);handle(pre, nextStart, start->right);}}return root;}
};

2.3 DFS序+层次记录

利用先序遍历的永远是从左到又这一特点，用一个pre[depth]数组来记录当前DFS遍历到的该层的左侧节点。当再次遍历到该层时，链接pre[depth]节点到当前节点，并更新。

class Solution {
public:void handle(Node *&pre, Node *&nextStart,Node *rt) {if (nullptr == rt) return ;if (!pre) {nextStart = rt;}else {pre->next = rt;}pre = rt;}void dfs(std::vector<Node*> &pre, Node *root, int depth) {if (nullptr == root)return;int sz = pre.size();if (sz == depth) {pre.push_back(root);}else {pre[depth]->next = root;pre[depth] = root;}dfs(pre, root->left, depth + 1);dfs(pre, root->right, depth + 1);}Node* connect(Node* root) {vector<Node *> pre;dfs(pre, root, 0);return root;}
};

3. Ref

03xf题解