LeetCode·701.二叉搜索树中的插入操作·递归
2023-09-27 14:26:29 时间
题目
示例![](https://img-blog.csdnimg.cn/0496e59f2da146e8948cc9ec39bfd913.png)
思路
解题思路
【利用二叉搜索树性质】
递归三部曲:
- 确定递归函数参数以及返回值
参数就是根节点指针,以及要插入元素,这里递归函数要不要有返回值呢?
可以有,也可以没有,但递归函数如果没有返回值的话,实现是比较麻烦的,下面也会给出其具体实现代码。
有返回值的话,可以利用返回值完成新加入的节点与其父节点的赋值操作。(下面会进一步解释)
递归函数的返回类型为节点类型TreeNode * 。
代码如下:
struct TreeNode* insertIntoBST(struct TreeNode* root, int val)
- 确定终止条件
终止条件就是找到遍历的节点为null的时候,就是要插入节点的位置了,并把插入的节点返回。
代码如下:
if(root == NULL)
{
struct TreeNode * node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
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将其接住。
作者:xun-ge-v
链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree/solution/-by-xun-ge-v-mzpz/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
if(root == NULL)
{
struct TreeNode * node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
if(root->val < val)
root->right = insertIntoBST(root->right, val);
else
root->left = insertIntoBST(root->left, val);
return root;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree/solution/-by-xun-ge-v-mzpz/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 【LeetCode】根据身高重建队列 [M](贪心)
- 【LeetCode】验证二叉搜索树 [M]
- 【LeetCode】单词搜索 II [H](前缀树)
- 【LeetCode】摘樱桃 [H](记忆化搜索)
- 【LeetCode】两数相加
- LeetCode_动态规划_困难_1326.灌溉花园的最少水龙头数目
- LeetCode_贪心算法_中等_665.非递减数列
- LeetCode_二分搜索_容斥原理_困难_878.第 N 个神奇数字
- LeetCode_二叉搜索树_中等_538.把二叉搜索树转换为累加树
- LeetCode_二叉搜索树_中等_96.不同的二叉搜索树
- LeetCode_双指针_简单_26.删除有序数组中的重复项
- LeetCode_双指针_中等_18.四数之和
- LeetCode·139.单词拆分·递归·记忆化搜索·字典树
- LeetCode·669.修剪二叉搜索树·递归
- LeetCode·641.设计循环双端队列·循环双链表
- LeetCode——Palindrome Number
- [LeetCode] 450. Delete Node in a BST 删除二叉搜索树中的节点
- [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和
- [LeetCode] 272. Closest Binary Search Tree Value II 最近的二叉搜索树的值 II
- [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵
- [LeetCode] 212. Word Search II 词语搜索 II
- [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历
- leetcode算法:Distribute Candies
- leetcode 503 下一个更大的元素II
- leetcode 78 子集