题目简介：
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
1
2
3
4
5
6
7
8
9
| 给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和 插入的值: 5
|
你可以返回这个二叉搜索树:
1
2
3
4
5
| 4
/ \
2 7
/ \ /
1 3 5
|
或者这个树也是有效的:
5
/ \
2 7
/ \
1 3
\
4
提示：
- 给定的树上的节点数介于
0 和 10^4 之间
- 每个节点都有一个唯一整数值，取值范围从
0 到 10^8
-10^8 <= val <= 10^8- 新值和原始二叉搜索树中的任意节点值都不同
思路：
递归，每次与root -> val进行比较，从而向右子树或左子树移动。
当!root -> left && root -> val > val时，则将结点放置在root的左子树上。
当!root -> right && root -> val < val时，则将结点放置在root的右子树上。
需要注意的是初始root为空的情况。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
class Solution {
public:
void dfs(TreeNode* root, int val){
if(!root -> left && root -> val > val){
TreeNode* node = new TreeNode(val);
root -> left = node;
return;
}
if(!root -> right && root -> val < val){
TreeNode* node = new TreeNode(val);
root -> right = node;
return;
}
if(root -> val < val)
dfs(root -> right, val);
else
dfs(root -> left, val);
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root)
return new TreeNode(val);
dfs(root, val);
return root;
}
};
|
