原题
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
给定二叉搜索树:
4
/ \
2 7
/ \
1 3和 插入的值: 5
你可以返回这个二叉搜索树:
4
/ \
2 7
/ \ /
1 3 5
或者这个树也是有效的:
5
/ \
2 7
/ \
1 3
\
4
解法
思想
与搜索操作类似,对于每个节点,我们将:
- 根据节点值与目标节点值的关系,搜索左子树或右子树;
- 重复步骤 1 直到到达外部节点;
- 根据节点的值与目标节点的值的关系,将新节点添加为其左侧或右侧的子节点。
如此递归。
代码
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(val<root.val){
if(root.left==null) root.left = new TreeNode(val);
else insertIntoBST(root.left,val);
}
if(val>root.val){
if(root.right==null) root.right = new TreeNode(val);
else insertIntoBST(root.right,val);
}
return root;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode701-%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%e4%b8%ad%e7%9a%84%e6%8f%92%e5%85%a5%e6%93%8d%e4%bd%9c/