网站开发中涉及的两种服务器,代运营电商平台公司,公主坟网站建设,开个大型购物网站需要多少钱解题思路#xff1a; 二叉搜索树特点#xff1a;中间节点大于所有左子树值#xff0c;小于所有右子树值。中序遍历是严格单调增序列。 再次明确#xff1a;二叉搜索树#xff0c;没有重复节点#xff0c;所以新插入的值也不可能和树里元素重复。 原因#xff1a;题目限制… 解题思路 二叉搜索树特点中间节点大于所有左子树值小于所有右子树值。中序遍历是严格单调增序列。 再次明确二叉搜索树没有重复节点所以新插入的值也不可能和树里元素重复。 原因题目限制 插入的值总能在叶子上找到一个合适的值插入其不会改变原有节点的位置。 这就导致这道题不会太难即找到一个合适的叶子将新值变成它的左或右孩子。 解题方法 递归 迭代 1.递归
由于二叉搜索树的有序性找到一个合适的叶子总是容易的可以根据值的大小关系选择向左还是向右。
public TreeNode insertIntoBST(TreeNode root, int val) {//找到合适的位置if(rootnull) return new TreeNode(val);//val往root的左子树找if(root.valval){root.leftinsertIntoBST(root.left,val);//将更新后的左子树重新赋值} else if (root.valval) {//val往root的右子树找root.rightinsertIntoBST(root.right,val);//将更新后的右子树重新赋值}return root;}
2.迭代
注意当root为null是也是有返回值的——new TreeNode(val)
该题也相当于是二叉搜索树种的查找操作不需要回溯不需要栈来模拟递归过程。
所以则道题目用迭代也非常简单且易于理解。
public TreeNode insertIntoBST2(TreeNode root, int val) {TreeNode curroot;while(cur!null){//向左插入if(cur.valval){if(cur.left!null){curcur.left;}else{//插入cur.leftnew TreeNode(val);break;}//向右插入} else if (cur.valval) {if(cur.right!null){curcur.right;}else{//插入cur.rightnew TreeNode(val);break;}}}return rootnull?new TreeNode(val):root;}
3.分析 时间复杂度 递归O(n) 迭代O(n) 空间复杂度 递归O(log2N) 迭代O(log2N)
