二叉树---二叉搜索树中的插入操作
题目:
给定二叉搜索树(BST)的根节点 root
和要插入树中的值 value
,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
思路:找到空节点插入新节点,由于树是二叉搜索树,故需判断访问的节点值与插入值的大小决定递归访问左子树还是右子树。
第一步:确定参数与返回值。参数为节点,插入值,返回值为树
第二步:确定终止条件。遇到空节点,则创建新节点,即插入节点,并把插入节点返回。
第三步:确定单层递归逻辑。如果节点值>插入值,则递归遍历左子树;如果节点值<插入值,则递归遍历右子树。
代码:
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null){
TreeNode node=new TreeNode(val);
return node;
}
if(root.val>val) root.left=insertIntoBST(root.left,val);
if(root.val<val) root.right=insertIntoBST(root.right,val);
return root;
}
原文地址:https://blog.csdn.net/m0_65096633/article/details/140712914
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!