LeetCode 701 Insert into a Binary Search Tree

题意

给定一颗 二叉搜索树 的根节点,和一个要插入的值,将值插入进去,并返回根节点

  • 保证原树中不存在新值
  • 只要保证返回的树同样也是 二叉搜索树 即可

例 :

1
2
3
4
5
6
7
给予树:
4
/ \
2 7
/ \
1 3
并且要插入的值:5

您可以返回此 二叉搜索树

1
2
3
4
5
     4
/ \
2 7
/ \ /
1 3 5

这棵树也有效:

1
2
3
4
5
6
7
     5
/ \
2 7
/ \
1 3
\
4

解法

因为是二叉搜索树,所以依次判断新值与每个节点的大小即可,大于当前节点,则判断此节点的右节点与新节点。小于当前节点,则判断此节点的左节点与新节点,直到子节点为空,那么再根据此节点的大小选择放到左侧还是右侧。

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
throw new IllegalArgumentException("Tree Root can not be empty");
}
TreeNode current = root;

TreeNode preNode = null;
while (current != null) {
preNode = current;
if (current.val < val) {
current = current.right;
} else if (current.val > val){
current = current.left;
}
}

if (preNode.val < val) {
System.out.println("1");
preNode.right = new TreeNode(val);
} else {
System.out.println("2");
preNode.left = new TreeNode(val);
}

return root;
}
}

Runtime: 1 ms, faster than 100.00% of Java online submissions for Insert into a Binary Search Tree.

Memory Usage: 39.8 MB, less than 94.61% of Java online submissions for Insert into a Binary Search Tree.

  • 本文作者: 赵俊
  • 本文链接: http://www.zhaojun.im/leetcode-701/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!