Keshawn_lu's Blog

Leetcode 701. 二叉搜索树中的插入操作

字数统计: 487阅读时长: 2 min
2020/09/30 Share

题目简介:

给定二叉搜索树(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

提示:

  • 给定的树上的节点数介于 010^4 之间
  • 每个节点都有一个唯一整数值,取值范围从 010^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
/**
* 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:

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;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: