seo外贸仿牌网站换域名,上海网站建设褐公洲司,学生个人主页制作,网站建设了流程文章目录 1. 题意2. 题解2.1 BFS2.2 BFS空间优化2.3 DFS序层次记录 3. Ref 1. 题意
在一颗树的同层之间用指针把他们链接起来。
填充每个节点的下一个右侧节点指针 II
2. 题解
2.1 BFS
用一个变量记录下同层最右侧的节点#xff0c;当遍历到时更新下一层的最右侧节点即可… 文章目录 1. 题意2. 题解2.1 BFS2.2 BFS空间优化2.3 DFS序层次记录 3. Ref 1. 题意
在一颗树的同层之间用指针把他们链接起来。
填充每个节点的下一个右侧节点指针 II
2. 题解
2.1 BFS
用一个变量记录下同层最右侧的节点当遍历到时更新下一层的最右侧节点即可。
class Solution {
public:Node* connect(Node* root) {Node *righMost root;queueNode * 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::vectorNode* 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) {vectorNode * pre;dfs(pre, root, 0);return root;}
};3. Ref
03xf题解
