题解：
二叉搜索树的插入操作非常简单，当val > root.val时，插入root的左子树, 当val < root.val时，插入root的右子树。
思路一：
递归，代码如下：
1
2
3
4
5
6
7
8
9
10
11
|
// 递归
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}else {
root.left = insertIntoBST(root.left,val);
}
return 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
|
// 迭代
public TreeNode insertIntoBST1(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
TreeNode node = root;
while (node != null){
if (val > node.val){
if (node.right == null){
node.right = new TreeNode(val);
return root;
}else {
node = node.right;
}
}else {
if (node.left == null){
node.left = new TreeNode(val);
return root;
}else {
node = node.left;
}
}
}
return new TreeNode(val);
}
|