用python做的网站多吗,化妆品公司网站源码,代理上网,网站版块策划文章目录1. 题目2. 解题2.1 递归2.2 循环2.3 O(1)空间复杂度1. 题目
给定一个完美二叉树#xff0c;其所有叶子节点都在同一层#xff0c;每个父节点都有两个子节点。二叉树定义如下#xff1a;
struct Node {int val;Node *left;Node *right;Node *next;
}填充它的每个 n…
文章目录1. 题目2. 解题2.1 递归2.2 循环2.3 O(1)空间复杂度1. 题目
给定一个完美二叉树其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {int val;Node *left;Node *right;Node *next;
}填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有 next 指针都被设置为 NULL 2. 解题
2.1 递归
class Solution {
public:Node* connect(Node* root) {if(root NULL || root-left NULL)return root;root-left-next root-right;if(root-next ! NULL)root-right-next root-next-left;connect(root-left);connect(root-right);return root;}
};2.2 循环
class Solution {
public:Node* connect(Node* root) {if(root NULL || root-left NULL)return root;queueNode* q;q.push(root);Node *p;int n;while(!q.empty()){n q.size();while(n--){p q.front();if(p-left ! NULL){q.push(p-left);q.push(p-right);p-left-next p-right;if(p-next ! NULL)p-right-next p-next-left;}q.pop();} }return root;}
};2.3 O(1)空间复杂度
利用next指针
class Solution {
public:Node* connect(Node* root) {if(root NULL || root-left NULL)return root;Node *parent root, *lvfirst, *prev;while(parent ! NULL){lvfirst parent-left;if(lvfirst ! NULL){while(parent){parent-left-next parent-right;prev parent-right;parent parent-next;if(parent)prev-next parent-left;}}parent lvfirst; }return root;}
};