题目描述
给定二叉搜索树(BST)的根结点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根结点。 保证原始二叉搜索树中不存在新值。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
样例
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和 插入的值: 5
你可以返回这个二叉搜索树:
4
/ \
2 7
/ \ /
1 3 5
或者这个树也是有效的:
5
/ \
2 7
/ \
1 3
\
4
算法
(数据结构基础) $O(n)$
- 按照二叉搜索树的性质,自顶向下查找插入的位置。
- 如果查找过程中发现相同的值,则直接返回。
- 如果
val
小于当前结点的值,则向左儿子查找;否则向右儿子查找,最后插入到叶结点上。 - 注意树为空的情况。
时间复杂度
- 时间复杂度与树的高度有关,最坏情况下需要 $O(n)$ 的时间。
空间复杂度
- 只需要新创建一个待插入的结点。
C++ 代码
/**
* 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:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root)
return new TreeNode(val);
TreeNode *cur = root, *fa = NULL;
while (cur) {
if (val == cur -> val)
return root;
else if (val < cur -> val) {
fa = cur;
cur = cur -> left;
} else {
fa = cur;
cur = cur -> right;
}
}
if (val < fa -> val)
fa -> left = new TreeNode(val);
else
fa -> right = new TreeNode(val);
return root;
}
};
大佬,为啥要记录
父节点
?这里父节点相当于当前节点的上一个节点。如果当前节点为空,需要在父节点下插入
因为不是recursion所以需要父节点