给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
例如,
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和 插入的值: 5
你可以返回这个二叉搜索树:
或者这个树也是有效的:
提示:
之间
<= val <=
抛砖引玉
思路
二叉搜索树:
即:左子树 < 根节点 < 右子树
那么遍历二叉树:
不打断原有子树,追加到叶子节点上。
指针从根节点开始递归遍历,每轮与根节点值比较,比较后指针更新到子树根节点,直到遇到空根节点即:
使用 val 对节点大小划分划分到与其差值最小的节点,生成节点值为 val 的子树追加到原树上
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var insertIntoBST = function(root, val) {
if (root === null) return new TreeNode(val)
if (root.val > val) {
//比该节点大查找左节点
root.left = insertIntoBST(root.left, val)
} else {
//比该节点小查找右节点
root.right = insertIntoBST(root.right, val)
}
return root
}
声明指针 node,模拟递归时指针变化:
从根节点开始:小于 val 指向左子树,不然指向右子树,直到遇到叶子节点
var postorderTraversal = function(root) {
if (root === null) return new TreeNode(val)
let node = root
while (node !== null) {
if (val < node.val) {
if (node.left === null) {
node.left = new TreeNode(val)
break
} else {
node = node.left
}
} else {
if (node.right === null) {
node.right = new TreeNode(val)
break
} else {
node = node.right
}
}
}
return root
}