leetcode 2020/9 每日一题
文章目录
- leetcode 2020/9 每日一题
- 2020/9/11: [组合总和 III](https://leetcode-cn.com/problems/combination-sum-iii/)
- 2020/9/12：[二叉树的层平均值](https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/)
- 2020/9/14: [二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
- 2020/9/18：[全排列 II](https://leetcode-cn.com/problems/permutations-ii/)
- 2020/9/20：[子集](https://leetcode-cn.com/problems/subsets/)
- 2020/9/21：[把二叉搜索树转换为累加树](https://leetcode-cn.com/problems/convert-bst-to-greater-tree/)
- 2020/09/23：[合并二叉树](https://leetcode-cn.com/problems/merge-two-binary-trees/)
- 2020/9/26： [路径总和 II](https://leetcode-cn.com/problems/path-sum-ii/)
- 2020/9/27： [二叉搜索树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
- 2020/9/28：[填充每个节点的下一个右侧节点指针 II](https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/)
- 2020/9/29：[二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
- 2020/9/30：[二叉搜索树中的插入操作](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
2020/9/11: 组合总和 III
问题 中等
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
my way
回溯法
循环加递归，还有改进空间，有重复计算过程
class Solution {
public:
vector<vector<int>> combinationSum(int k, int n,int m){
vector<vector<int>> tmp;
if(k==1){
for(int i=m;i<=9;i++)
if(i==n){
vector<int> tmp1;
tmp1.push_back(i);
tmp.push_back(tmp1);
}
return tmp;
}
for(int i=m;i<=10-k;i++){
vector<vector<int>> tmp0;
tmp0 = combinationSum(k-1,n-i,i+1) ;
for(int j=0;j<tmp0.size();j++){
tmp0[j].insert(tmp0[j].begin(),i);
}
tmp.insert(tmp.end(),tmp0.begin(),tmp0.end());
}
return tmp;
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> tmp;
for(int i=1;i<=10-k;i++){
vector<vector<int>> tmp0;
tmp0 = combinationSum(k-1,n-i,i+1);
for(int j=0;j<tmp0.size();j++){
tmp0[j].insert(tmp0[j].begin(),i);
}
tmp.insert(tmp.end(),tmp0.begin(),tmp0.end());
}
return tmp;
}
};
- 时间复杂度 O(k!)
- 空间复杂度 空间复杂度：O(M)。temp 数组的空间代价是 O(k)，递归栈空间的代价是 O(M)，故空间复杂度为 O(M + k) = O(M)
官方解答
思路类似于我的方法，都是寻找所有组合方法一个个判断。
class Solution{
public:
vector<int> temp;
vector<vector<int>> ans;
void dfs(int cur,int n, int k, int sum){
if(temp.size() + (n-cur +1)<k || temp.size() >k){
return;
}
if(temp.size() == k && accumulate(temp.begin(),temp.end(),0) == sum){
ans.push_back(temp);
return;
}
temp.push_back(cur);
dfs(cur+1,n,k,sum);
temp.pop_back();
dfs(cur+1,n,k,sum);
}
vector<vector<int>> combinationSum3(int k,int n){
dfs(1,9,k,n);
return ans;
}
}
- 时间复杂度：O({M \choose k} \times k)O(( kM)×k)，其中 M 为集合的大小，本题中 M 固定为 9。一共有 M \choose k( kM ) 个组合，每次判断需要的时间代价是 O(k)。
- 空间复杂度：O(M)。temp 数组的空间代价是 O(k)，递归栈空间的代价是 O(M)，故空间复杂度为 O(M + k) = O(M)
2020/9/12：二叉树的层平均值
问题 简单
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
输入：
3
/
9 20
/
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
my way
使用队列层次遍历二叉树，并使用另一个队列作为flag，标志每一层的结束。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> s;
queue<int> flag;
vector<double> result;
double sum_cur=0;
double l = 0;
s.push(root);
flag.push(0);
while(!s.empty()){
int tmp=flag.front();
TreeNode* cur = s.front();
s.pop();
flag.pop();
sum_cur+=cur->val;
l++;
if(flag.empty() || tmp!= flag.front()){
result.push_back(sum_cur/l);
l=0;
sum_cur=0;
}
if(cur->left!=NULL){
s.push(cur->left);
flag.push(!tmp);
}
if(cur->right!=NULL){
s.push(cur->right);
flag.push(!tmp);
}
}
return result;
}
};
- 时间复杂度O(n), 其中n是二叉树中的节点个数。
- 空间复杂度O(n)
官方解答之 广度优先遍历
类似于我的方法。
比我的更好，不需要flag，直接将每一层的队列节点全部取出，需要在遍历每一层之前获取每一层的size。
class Solution{
public:
vector<double> averageOfLevels(TreeNode* root) {
auto averages = vector<double>();
auto q = queue<TreeNode*>();
q.push(root);
while (!q.empty()) {
double sum = 0;
int size = q.size();
for (int i = 0; i < size; i++) {
auto node = q.front();
q.pop();
sum += node->val;
auto left = node->left, right = node->right;
if (left != nullptr) {
q.push(left);
}
if (right != nullptr) {
q.push(right);
}
}
averages.push_back(sum / size);
}
return averages;
}
};
- 时间复杂度：O(n)，其中 n 是二叉树中的节点个数
- 空间复杂度：O(n)
官方解答之 深度优先遍历
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
auto counts = vector<int>();
auto sums = vector<double>();
dfs(root, 0, counts, sums);
auto averages = vector<double>();
int size = sums.size();
for (int i = 0; i < size; i++) {
averages.push_back(sums[i] / counts[i]);
}
return averages;
}
void dfs(TreeNode* root, int level, vector<int> &counts, vector<double> &sums) {
if (root == nullptr) {
return;
}
if (level < sums.size()) {
sums[level] += root->val;
counts[level] += 1;
} else {
sums.push_back(1.0 * root->val);
counts.push_back(1);
}
dfs(root->left, level + 1, counts, sums);
dfs(root->right, level + 1, counts, sums);
}
};
时间复杂度：O(n)，其中 nn 是二叉树中的节点个数。
深度优先搜索需要对每个节点访问一次，对于每个节点，维护两个数组的时间复杂度都是 O(1)，因此深度优先搜索的时间复杂度是 O(n)。
遍历结束之后计算每层的平均值的时间复杂度是 O(h)，其中 hh 是二叉树的高度，任何情况下都满足 h≤n。
因此总时间复杂度是 O(n)。空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于两个数组的大小和递归调用的层数，两个数组的大小都等于二叉树的高度，递归调用的层数不会超过二叉树的高度，最坏情况下，二叉树的高度等于节点个数
2020/9/14: 二叉树的中序遍历
问题
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归解法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> result ;
vector<int> inorderTraversal(TreeNode* root) {
if(root==NULL)
return result;
dfs(root);
return result;
}
void dfs(TreeNode* root){
if(root==NULL)
return ;
dfs(root->left);
result.push_back(root->val);
dfs(root->right);
return;
}
};
- 时间复杂度O (n) ,n为二叉树的节点数
- 空间复杂度O(n), （不包括结果占用的空间） 递归的次数，最坏情况下为n
迭代
非递归算法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while(root != nullptr || !stk.empty()){
while(root!=nullptr){
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
- 时间复杂度:O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
- 空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
Morris中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode *predecessor = nullptr;
while (root != nullptr) {
if (root->left != nullptr) {
// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
predecessor = root->left;
while (predecessor->right != nullptr && predecessor->right != root) {
predecessor = predecessor->right;
}
// 让 predecessor 的右指针指向 root，继续遍历左子树
if (predecessor->right == nullptr) {
predecessor->right = root;
root = root->left;
}
// 说明左子树已经访问完了，我们需要断开链接
else {
res.push_back(root->val);
predecessor->right = nullptr;
root = root->right;
}
}
// 如果没有左孩子，则直接访问右孩子
else {
res.push_back(root->val);
root = root->right;
}
}
return res;
}
};
- 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为O(2n)=O(n)。
- 空间复杂度：O(1)。
2020/9/18：全排列 II
问题 中等
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
我的程序
莫得，我没做出来。
搜索回溯
class Solution{
vector<int> vis;
public:
void backtrack(vector<int>& nums,vector<int>>& ans,int idx,vector<int>& perm){
if(idx == nums.size()){
ans.emplace_back(perm);
return;
}
for(int i=0;i<(int)nums.size();++i){
if(vis[i] || (i>0 && nums[i] == nums[i-1] && !vis[i-1])){
continue;
}
perm.emplace_back(nums[i]);
vis[i] = 1;
backtrack(nums,ans,idx+1,perm);
vis[i] = 0;
perm.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums){
vector<vector<int>> ans;
vector<int> perm;
vis.resize(nums.size());
sort(nums.begin().nums.end());
backtrack(nums,ans,0,perm);
return ans;
}
}
- 时间复杂度O(n*n!),其中n为序列的长度
- 空间复杂度O(n)
2020/9/20：子集
问题
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
my way
回溯搜索法
class Solution {
public:
vector<vector<int>> result;
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> tmp;
backtrack(tmp,nums,0);
return result;
}
void backtrack(vector<int> tmp,vector<int>& nums,int t){
if(nums.begin()+t == nums.end()){
result.push_back(tmp);
return;
}
backtrack(tmp,nums,t+1);
tmp.push_back(*(nums.begin()+t));
backtrack(tmp,nums,t+1);
return;
}
};
- 时间复杂度
- 空间复杂度
不会算。。。。
迭代法实现子集枚举
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
}
- 时间复杂度：O(n*2^n)一共 2^n个状态，每种状态需要O(n) 的时间来构造子集。
- 空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价
递归法实现自己枚举
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
void dfs(int cur, vector<int>& nums) {
if (cur == nums.size()) {
ans.push_back(t);
return;
}
t.push_back(nums[cur]);
dfs(cur + 1, nums);
t.pop_back();
dfs(cur + 1, nums);
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(0, nums);
return ans;
}
};
- 时间复杂度：O(n * 2 ^ n) )。一共 2^n个状态，每种状态需要O(n) 的时间来构造子集。
- 空间复杂度 O(n)。临时数组 tt 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。
2020/9/21：把二叉搜索树转换为累加树
问题
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树:
5
/
2 13
输出: 转换为累加树:
18
/
20 13
反序中序遍历
class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root){
if(root != nullptr){
convertBST(root->right);
sum+=root->val;
root->val=sum;
convertBST(root->left);
}
return root;
}
};
- 时间复杂度O(n)，n是二叉树的节点数
- 空间复杂度O(n), 为递归过程中的栈的开销，平均情况下O(logn),最坏情况下为链状，O(n).
2020/09/23：合并二叉树
**问题 ** 简单
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
深度优先搜索
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(t1==nullptr)
return t2;
if(t2==nullptr)
return t1;
TreeNode* root=new TreeNode();
root->val=t1->val+t2->val;
root->right=mergeTrees(t1->right,t2->right);
root->left=mergeTrees(t1->left,t2->left);
return root;
}
};
- 时间复杂度O(min(m,n)) m, n为2个树各自节点个数
- 时间复杂度O(min(m,n)
2020/9/26： 路径总和 II
问题
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
深度优先搜索
class Solution {
public:
vector<vector<int>> result;
vector<int> cur_num;
int cur_sum=0;
void dfs(TreeNode* root, int sum){
if(root==nullptr)
return;
cur_num.push_back(root->val);
cur_sum+=root->val;
if(cur_sum==sum && root->right==nullptr && root->left==nullptr){
result.push_back(cur_num);
}
else{
dfs(root->left,sum);
dfs(root->right,sum);
}
cur_num.pop_back();
cur_sum-=root->val;
return;
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
dfs(root,sum);
return result;
}
};
- 时间复杂度O(n^2) ,n为节点数,在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。此时，路径的数目为 O(N)，并且每一条路径的节点个数也为 O(N)，因此要将这些路径全部添加进答案中，时间复杂度为 O(N^2)
- 空间复杂度O(n), path空间，最坏情况下n
2020/9/27： 二叉搜索树的最近公共祖先
问题 简单
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
一次遍历
根据二叉搜索树的特点可知，从根节点开始遍历，若qp的值都小于当前节点的值，则当前节点指向左子树，反之则指向右子树；若当前节点的值位于中间位置，则当前节点应当是公共祖先节点。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* curnode=root;
while(true){
if(curnode->val > p->val && curnode->val > q->val){
curnode = curnode->left;
}
else if(curnode->val < p->val && curnode->val < q->val){
curnode = curnode->right;
}
else
break;
}
return curnode;
}
};
- 时间复杂度O(n) n为节点数
- 空间复杂度O(1)
2020/9/28：填充每个节点的下一个右侧节点指针 II
问题 中等
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
树中的节点数小于 6000
-100 <= node.val <= 100
广度优先遍历
使用了一个队列空间
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> tmp;
if(root==nullptr)
return root;
tmp.push(root);
while(!tmp.empty()){
int len = tmp.size();
for(int i=0;i<len;i++){
Node* cur = tmp.front();
tmp.pop();
if(cur->left!=nullptr)
tmp.push(cur->left);
if(cur->right!=nullptr)
tmp.push(cur->right);
if(i==len-1){
cur->next = NULL;
}
else{
cur->next = tmp.front();
}
}
}
return root;
}
};
- 时间复杂度O(n);
- 空间复杂度O(n);
使用已建立的next指针
降低空间复杂度。。。
不会做，看不懂！！！！！！！！！！
先抄一段代码，CV大法好。
具体来说：
从根节点开始。因为第 00 层只有一个节点，不需要处理。可以在上一层为下一层建立 \rm nextnext 指针。该方法最重要的一点是：位于第 xx 层时为第 x + 1x+1 层建立 \rm nextnext 指针。一旦完成这些连接操作，移至第 x + 1x+1 层为第 x + 2x+2 层建立 \rm nextnext 指针。
当遍历到某层节点时，该层节点的 \rm nextnext 指针已经建立。这样就不需要队列从而节省空间。每次只要知道下一层的最左边的节点，就可以从该节点开始，像遍历链表一样遍历该层的所有节点。
public:
void handle(Node* &last, Node* &p, Node* &nextStart) {
if (last) {
last->next = p;
}
if (!nextStart) {
nextStart = p;
}
last = p;
}
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
Node *start = root;
while (start) {
Node *last = nullptr, *nextStart = nullptr;
for (Node *p = start; p != nullptr; p = p->next) {
if (p->left) {
handle(last, p->left, nextStart);
}
if (p->right) {
handle(last, p->right, nextStart);
}
}
start = nextStart;
}
return root;
}
};
- 时间复杂度：O(N)。分析同「方法一」。
- 空间复杂度：O(1)
2020/9/29：二叉树的后序遍历
问题 中等
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> result;
vector<int> postorderTraversal(TreeNode* root) {
postorder(root);
return result;
}
void postorder(TreeNode* root){
if(root==nullptr)
return;
postorder(root->left);
postorder(root->right);
result.push_back(root->val);
return;
}
};
- 时间复杂度O(n), n为节点数
- 空间复杂度O(n), 递归隐式栈占用的空间，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。
迭代
隐式栈变成显式栈
后序遍历 左-右-中 ， 可以改成中-右-左，最后翻转下
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if(root==nullptr)
return result;
stack<TreeNode*> tmp;
tmp.push(root);
while(!tmp.empty()){
TreeNode* cur = tmp.top();
tmp.pop();
result.push_back(cur->val);
if(cur->left!=nullptr){
tmp.push(cur->left);
}
if(cur->right!=nullptr){
tmp.push(cur->right);
}
}
reverse(result.begin(),result.end());
return result;
}
};
- 时间复杂度O(n)
- 空间复杂度O(n)
2020/9/30：二叉搜索树中的插入操作
问题 中等
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和 插入的值: 5
你可以返回这个二叉搜索树:
4
/ \
2 7
/ \ /
1 3 5
或者这个树也是有效的:
5
/ \
2 7
/ \
1 3
\
4
提示：
给定的树上的节点数介于 0 和 10^4 之间
每个节点都有一个唯一整数值，取值范围从 0 到 10^8
-10^8 <= val <= 10^8
新值和原始二叉搜索树中的任意节点值都不同
递归
根据二叉搜索树的性质，插入节点的话，若该值大于当前节点值，这肯定要插到当前节点的右子树，否则插入到左子树。递归下去，直到当前节点为空，则插入该值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==nullptr){
root = new TreeNode(val);
return root;
}
if(val > root->val)
root->right= insertIntoBST(root->right,val);
else
root->left = insertIntoBST(root->left,val);
return root;
}
};
- 时间复杂度O(n) ,n为节点数目，最坏情况下，该树为链状。
- 空间复杂度O(n) 递归的栈开销。
模拟（算是迭代吧）
算法和上一个解法一样
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
TreeNode* pos = root;
while (pos != nullptr) {
if (val < pos->val) {
if (pos->left == nullptr) {
pos->left = new TreeNode(val);
break;
} else {
pos = pos->left;
}
} else {
if (pos->right == nullptr) {
pos->right = new TreeNode(val);
break;
} else {
pos = pos->right;
}
}
}
return root;
}
};
- 时间复杂度O(n)
root = new TreeNode(val);
return root;
}
if(val > root->val)
root->right= insertIntoBST(root->right,val);
else
root->left = insertIntoBST(root->left,val);
return root;
}
};
- 时间复杂度O(n) ,n为节点数目，最坏情况下，该树为链状。
- 空间复杂度O(n) 递归的栈开销。
**模拟（算是迭代吧）**
算法和上一个解法一样
~~~cpp
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
TreeNode* pos = root;
while (pos != nullptr) {
if (val < pos->val) {
if (pos->left == nullptr) {
pos->left = new TreeNode(val);
break;
} else {
pos = pos->left;
}
} else {
if (pos->right == nullptr) {
pos->right = new TreeNode(val);
break;
} else {
pos = pos->right;
}
}
}
return root;
}
};
- 时间复杂度O(n)
- 空间复杂度O(1)
9月水水水！！
版权声明：本文为jiamenghu原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。