LeetCode·701.二叉搜索树中的插入操作·递归
题目
示例
思路
解题思路
【利用二叉搜索树性质】
递归三部曲：
- 确定递归函数参数以及返回值
参数就是根节点指针，以及要插入元素，这里递归函数要不要有返回值呢？
可以有，也可以没有，但递归函数如果没有返回值的话，实现是比较麻烦的，下面也会给出其具体实现代码。
有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作。（下面会进一步解释）
递归函数的返回类型为节点类型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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。