专业烟台房产网站建设,河南省财政厅经济建设网站,广州免费律师援助,做网站赚钱的时代过去了吗题目#xff1a;
给定二叉搜索树#xff08;BST#xff09;的根节点 root 和要插入树中的值 value #xff0c;将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 #xff0c;新值和原始二叉搜索树中的任意节点值都不同。
注意#xff0c;可能存在多…题目
给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 新值和原始二叉搜索树中的任意节点值都不同。
注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1 输入root [4,2,7,1,3], val 5 输出[4,2,7,1,3,5] 解释另一个满足题目要求可以通过的树是
示例 2 输入root [40,20,60,10,30,50,70], val 25 输出[40,20,60,10,30,50,70,null,null,25]
示例 3 输入root [4,2,7,1,3,null,null,null,null,null,null], val 5 输出[4,2,7,1,3,5]
提示
树中的节点数将在 [0, 104]的范围内。-108 Node.val 108所有值 Node.val 是 独一无二 的。-108 val 108保证 val 在原始BST中不存在。 思路
如下演示视频中可以看出只要按照二叉搜索树的规则去遍历遇到空节点就插入节点就可以了。
例如插入元素10 需要找到末尾节点插入便可一样的道理来插入元素15插入元素0插入元素6需要调整二叉树的结构么 并不需要。。
只要遍历二叉搜索树找到空节点 插入元素就可以了那么这道题其实就简单了。
接下来就是遍历二叉搜索树的过程了。
递归法
递归三部曲
确定递归函数参数以及返回值
参数就是根节点指针以及要插入元素这里递归函数要不要有返回值呢
可以有也可以没有但递归函数如果没有返回值的话实现是比较麻烦的。
有返回值的话可以利用返回值完成新加入的节点与其父节点的赋值操作。
递归函数的返回类型为节点类型TreeNode * 。
代码如下
TreeNode* insertIntoBST(TreeNode* root, int val)确定终止条件
终止条件就是找到遍历的节点为null的时候就是要插入节点的位置了并把插入的节点返回。
代码如下
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;到这里应该能感受到如何通过递归函数返回值完成了新加入节点的父子关系赋值操作了下一层将加入节点返回本层用root-left或者root-right将其接住。
迭代法
在迭代法遍历的过程中需要记录一下当前遍历的节点的父节点这样才能做插入节点的操作。
因为迭代的循环退出后当前节点cur为NULL且cur的位置就是要插入元素的位置所以要记录该节点的父节点parent进行赋值。 代码
递归法
class Solution {
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);else if(root-val val) root-right insertIntoBST(root-right, val);return root;}
};迭代法
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root NULL){TreeNode* node new TreeNode(val);return node;}TreeNode* cur root; // 当前节点TreeNode* parent root; // 这个很重要需要记录上一个节点否则无法赋值新节点while(cur ! NULL){ // 退出循环后此时的cur为空且cur的位置就是插入元素的位置所以根据cur的父节点parent赋值parent cur;if(cur-val val) cur cur-left;else if(cur-val val) cur cur-right;}// 根据parent赋值TreeNode* node new TreeNode(val);if(parent-val val) parent-left node;else parent-right node;return root;}
};总结
首先在二叉搜索树中的插入操作不用恐惧其重构搜索树其实根本不用重构。
然后在递归中重点讲了如何通过递归函数的返回值完成新加入节点和其父节点的赋值操作并强调了搜索树的有序性。
最后依然给出了迭代的方法迭代的方法就需要记录当前遍历节点的父节点了这个和没有返回值的递归函数实现的代码逻辑是一样的。 参考
代码随想录
