701. 二叉搜索树中的插入操作
题目描述
输入一棵二叉搜索树的根节点 root（用层序数组表示，可能为空树）和一个整数 val。保证 val 与树中已有的所有值都不同。
把 val 作为新节点加入这棵树，并保证加入后仍是二叉搜索树。返回加入后树的根节点。
合法的插入位置可能不止一种，返回任意一种满足二叉搜索树性质的结果都算正确。
示例 1
输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5]
解释：5 比 4 大、比 7 小，成为 7 的左孩子。
示例 2
输入：root = [40,20,60,10,30,50,70], val = 25 输出：[40,20,60,10,30,50,70,null,null,25]
解释：25 沿 40、20、30 向下，成为 30 的左孩子。
示例 3
输入：root = [4,2,7,1,3,null,null,null,null,null,null] val = 5 输出：[4,2,7,1,3,5]
解释：输入末尾的 null 只是空位，结果与示例 1 相同。
数据范围
- 节点数在
[0, 10^4]范围内。 -10^8 <= Node.val <= 10^8- 所有
Node.val互不相同。 -10^8 <= val <= 10^8- 保证
val不在原树中。
解题思路
最简单的做法是把新值放到一个空位上，成为叶子：像查找一样从根往下走，val 比当前节点小就往左、大就往右；在要去的方向上一旦遇到空位，就在那里新建节点挂上去。原有节点完全不动，因此 BST 性质保持不变。空树时新节点本身就是根。
为什么正确
新节点最终所在的位置，一定在它应处的值区间内：路径上每次往左都给它加了一个上界，往右都加了一个下界。
复杂度分析
时间 O(h)，h 是树高；空间 O(1)（迭代写法）。
易错点
要返回的是原来的根 root，而不是新建的节点；空树时才返回新节点。答案不唯一，判题只检查结果是不是包含全部值的合法 BST。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
node = root
while True:
if val < node.val:
if not node.left:
node.left = TreeNode(val)
return root
node = node.left
else:
if not node.right:
node.right = TreeNode(val)
return root
node = node.rightclass Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null)
return new TreeNode(val);
TreeNode node = root;
while (true) {
if (val < node.val) {
if (node.left == null) {
node.left = new TreeNode(val);
return root;
}
node = node.left;
} else {
if (node.right == null) {
node.right = new TreeNode(val);
return root;
}
node = node.right;
}
}
}
}class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root)
return new TreeNode(val);
TreeNode* node = root;
while (true) {
if (val < node->val) {
if (!node->left) {
node->left = new TreeNode(val);
return root;
}
node = node->left;
} else {
if (!node->right) {
node->right = new TreeNode(val);
return root;
}
node = node->right;
}
}
}
};func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
node := root
for {
if val < node.Val {
if node.Left == nil {
node.Left = &TreeNode{Val: val}
return root
}
node = node.Left
} else {
if node.Right == nil {
node.Right = &TreeNode{Val: val}
return root
}
node = node.Right
}
}
}var insertIntoBST = function(root, val) {
if (!root)
return new TreeNode(val);
let node = root;
while (true) {
if (val < node.val) {
if (!node.left) {
node.left = new TreeNode(val);
return root;
}
node = node.left;
} else {
if (!node.right) {
node.right = new TreeNode(val);
return root;
}
node = node.right;
}
}
};function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
if (!root)
return new TreeNode(val);
let node: TreeNode = root;
while (true) {
if (val < node.val) {
if (!node.left) {
node.left = new TreeNode(val);
return root;
}
node = node.left;
} else {
if (!node.right) {
node.right = new TreeNode(val);
return root;
}
node = node.right;
}
}
};