递归
解题思路
二叉搜索树的中序遍历是递增序列，左节点的值 < 根节点的值 < 右节点的值；
- 若
val < root.val递归左子树；- 若
val > root.val递归右子树；终止条件，
root == null的时候返回新建 val 的节点；
复杂度
-
时间复杂度：
O(N)，其中 N 为树中节点的数目，最坏情况下，需要将值插入到树的最深的叶子结点上，而叶子节点最深为O(N)； -
空间复杂度：
O(1)，只使用了常数大小的空间；
代码实现
var insertIntoBST = function (root, val) {
if (root === null) return new TreeNode(val);
if (root.val > val) {
root.left = insertIntoBST(root.left, val);
} else if (root.val < val) {
root.right = insertIntoBST(root.right, val);
}
return root;
};
迭代
复杂度
-
时间复杂度：
O(N)，其中 N 为树中节点的数目，最坏情况下，需要将值插入到树的最深的叶子结点上，而叶子节点最深为O(N)； -
空间复杂度：
O(1)，只使用了常数大小的空间；
代码实现
var insertIntoBST = function (root, val) {
if (root === null) return new TreeNode(val);
let curr = root;
while (curr !== null) {
if (val < curr.val) {
if (curr.left === null) {
curr.left = new TreeNode(val);
break;
} else {
curr = curr.left;
}
} else {
if (curr.right === null) {
curr.right = new TreeNode(val);
break;
} else {
curr = curr.right;
}
}
}
return root;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 503. 下一个更大元素Ⅱ
上一篇
评论
