聊聊二叉搜索树中的插入操作

二叉搜索树中的插入操作

题目链接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

成都创新互联于2013年开始，是专业互联网技术服务公司，拥有项目网站设计制作、成都做网站网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元临猗做网站,已为上家服务,为临猗各地企业和个人服务,联系电话:13518219792

给定二叉搜索树(BST)的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

提示：

  • 给定的树上的节点数介于 0 和 10^4 之间
  • 每个节点都有一个唯一整数值，取值范围从 0 到 10^8
  • -10^8 <= val <= 10^8
  • 新值和原始二叉搜索树中的任意节点值都不同

思路

其实这道题目其实是一道简单题目，但是题目中的提示：有多种有效的插入方式，还可以重构二叉搜索树，一下子吓退了不少人，瞬间感觉题目复杂了很多。

其实可以不考虑题目中提示所说的改变树的结构的插入方式。

如下演示视频中可以看出：只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。

二叉搜索树中的插入操作

例如插入元素10 ，需要找到末尾节点插入便可，一样的道理来插入元素15，插入元素0，插入元素6，需要调整二叉树的结构么?并不需要。。

只要遍历二叉搜索树，找到空节点 插入元素就可以了，那么这道题其实就简单了。

接下来就是遍历二叉搜索树的过程了。

递归

递归三部曲：

  • 确定递归函数参数以及返回值

参数就是根节点指针，以及要插入元素，这里递归函数要不要有返回值呢?

可以有，也可以没有，但递归函数如果没有返回值的话，实现是比较麻烦的，下面也会给出其具体实现代码。

有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作。(下面会进一步解释)

递归函数的返回类型为节点类型TreeNode * 。

代码如下：

 
 
 
 
    
  
  
  
  
  1. TreeNode* insertIntoBST(TreeNode* root, int val)
    2.
  • 确定终止条件

终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。

代码如下：

 
 
 
 
    
  
  
  
  
  1. if (root == NULL) {
    2. 
  
  
  
  
  2.     TreeNode* node = new TreeNode(val);
    3. 
  
  
  
  
  3.     return node;
    4. 
  
  
  
  
  4. }
    5.

这里把添加的节点返回给上一层，就完成了父子节点的赋值操作了，详细再往下看。

  • 确定单层递归的逻辑

此时要明确，需要遍历整棵树么?

别忘了这是搜索树，遍历整颗搜索树简直是对搜索树的侮辱，哈哈。

搜索树是有方向了，可以根据插入元素的数值，决定递归方向。

代码如下：

 
 
 
 
    
  
  
  
  
  1. if (root->val > val) root->left = insertIntoBST(root->left, val);
    2. 
  
  
  
  
  2. if (root->val < val) root->right = insertIntoBST(root->right, val);
    3. 
  
  
  
  
  3. return root;
    4.

到这里，大家应该能感受到，如何通过递归函数返回值完成了新加入节点的父子关系赋值操作了，下一层将加入节点返回，本层用root->left或者root->right将其接住。

整体代码如下：

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2. public:
    3. 
  
  
  
  
  3.     TreeNode* insertIntoBST(TreeNode* root, int val) {
    4. 
  
  
  
  
  4.         if (root == NULL) {
    5. 
  
  
  
  
  5.             TreeNode* node = new TreeNode(val);
    6. 
  
  
  
  
  6.             return node;
    7. 
  
  
  
  
  7.         }
    8. 
  
  
  
  
  8.         if (root->val > val) root->left = insertIntoBST(root->left, val);
    9. 
  
  
  
  
  9.         if (root->val < val) root->right = insertIntoBST(root->right, val);
    10. 
  
  
  
  
  10.         return root;
    11. 
  
  
  
  
  11.     }
    12. 
  
  
  
  
  12. };
    13.

可以看出代码并不复杂。

刚刚说了递归函数不用返回值也可以，找到插入的节点位置，直接让其父节点指向插入节点，结束递归，也是可以的。

那么递归函数定义如下：

 
 
 
 
    
  
  
  
  
  1. TreeNode* parent; // 记录遍历节点的父节点
    2. 
  
  
  
  
  2. void traversal(TreeNode* cur, int val)
    3.

没有返回值，需要记录上一个节点(parent)，遇到空节点了，就让parent左孩子或者右孩子指向新插入的节点。然后结束递归。

代码如下：

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2. private:
    3. 
  
  
  
  
  3.     TreeNode* parent;
    4. 
  
  
  
  
  4.     void traversal(TreeNode* cur, int val) {
    5. 
  
  
  
  
  5.         if (cur == NULL) {
    6. 
  
  
  
  
  6.             TreeNode* node = new TreeNode(val);
    7. 
  
  
  
  
  7.             if (val > parent->val) parent->right = node;
    8. 
  
  
  
  
  8.             else parent->left = node;
    9. 
  
  
  
  
  9.             return;
    10. 
  
  
  
  
  10.         }
    11. 
  
  
  
  
  11.         parent = cur;
    12. 
  
  
  
  
  12.         if (cur->val > val) traversal(cur->left, val);
    13. 
  
  
  
  
  13.         if (cur->val < val) traversal(cur->right, val);
    14. 
  
  
  
  
  14.         return;
    15. 
  
  
  
  
  15.     }
    16. 
  
  
  
  
  16. 
  
  
  
  
  17. public:
    18. 
  
  
  
  
  18.     TreeNode* insertIntoBST(TreeNode* root, int val) {
    19. 
  
  
  
  
  19.         parent = new TreeNode(0);
    20. 
  
  
  
  
  20.         if (root == NULL) {
    21. 
  
  
  
  
  21.             root = new TreeNode(val);
    22. 
  
  
  
  
  22.         }
    23. 
  
  
  
  
  23.         traversal(root, val);
    24. 
  
  
  
  
  24.         return root;
    25. 
  
  
  
  
  25.     }
    26. 
  
  
  
  
  26. };
    27.

可以看出还是麻烦一些的。

我之所以举这个例子，是想说明通过递归函数的返回值完成父子节点的赋值是可以带来便利的。

网上千变一律的代码，可能会误导大家认为通过递归函数返回节点 这样的写法是天经地义，其实这里是有优化的!

迭代

再来看看迭代法，对二叉搜索树迭代写法不熟悉，可以看这篇：二叉树：二叉搜索树登场!

在迭代法遍历的过程中，需要记录一下当前遍历的节点的父节点，这样才能做插入节点的操作。

在530.二叉搜索树的最小绝对差和501.二叉搜索树中的众数中，都是用了记录pre和cur两个指针的技巧，本题也是一样的。

代码如下：

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2. public:
    3. 
  
  
  
  
  3.     TreeNode* insertIntoBST(TreeNode* root, int val) {
    4. 
  
  
  
  
  4.         if (root == NULL) {
    5. 
  
  
  
  
  5.             TreeNode* node = new TreeNode(val);
    6. 
  
  
  
  
  6.             return node;
    7. 
  
  
  
  
  7.         }
    8. 
  
  
  
  
  8.         TreeNode* cur = root;
    9. 
  
  
  
  
  9.         TreeNode* parent = root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点
    10. 
  
  
  
  
  10.         while (cur != NULL) {
    11. 
  
  
  
  
  11.             parent = cur;
    12. 
  
  
  
  
  12.             if (cur->val > val) cur = cur->left;
    13. 
  
  
  
  
  13.             else cur = cur->right;
    14. 
  
  
  
  
  14.         }
    15. 
  
  
  
  
  15.         TreeNode* node = new TreeNode(val);
    16. 
  
  
  
  
  16.         if (val < parent->val) parent->left = node;// 此时是用parent节点的进行赋值
    17. 
  
  
  
  
  17.         else parent->right = node;
    18. 
  
  
  
  
  18.         return root;
    19. 
  
  
  
  
  19.     }
    20. 
  
  
  
  
  20. };
    21.

总结

首先在二叉搜索树中的插入操作，大家不用恐惧其重构搜索树，其实根本不用重构。

然后在递归中，我们重点讲了如果通过递归函数的返回值完成新加入节点和其父节点的赋值操作，并强调了搜索树的有序性。

最后依然给出了迭代的方法，迭代的方法就需要记录当前遍历节点的父节点了，这个和没有返回值的递归函数实现的代码逻辑是一样的。

其他语言版本

Java

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2.     public TreeNode insertIntoBST(TreeNode root, int val) {
    3. 
  
  
  
  
  3.         if (root == null) return new TreeNode(val);
    4. 
  
  
  
  
  4.         TreeNode newRoot = root;
    5. 
  
  
  
  
  5.         TreeNode pre = root;
    6. 
  
  
  
  
  6.         while (root != null) {
    7. 
  
  
  
  
  7.             pre = root;
    8. 
  
  
  
  
  8.             if (root.val > val) {
    9. 
  
  
  
  
  9.                 root = root.left;
    10. 
  
  
  
  
  10.             } else if (root.val < val) {
    11. 
  
  
  
  
  11.                 root = root.right;
    12. 
  
  
  
  
  12.             }
    13. 
  
  
  
  
  13.         }
    14. 
  
  
  
  
  14.         if (pre.val > val) {
    15. 
  
  
  
  
  15.             pre.left = new TreeNode(val);
    16. 
  
  
  
  
  16.         } else {
    17. 
  
  
  
  
  17.             pre.right = new TreeNode(val);
    18. 
  
  
  
  
  18.         }
    19. 
  
  
  
  
  19. 
  
  
  
  
  20.         return newRoot;
    21. 
  
  
  
  
  21.     }
    22. 
  
  
  
  
  22. }
    23.

递归法

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2.     public TreeNode insertIntoBST(TreeNode root, int val) {
    3. 
  
  
  
  
  3.         return buildTree(root, val);
    4. 
  
  
  
  
  4.     }
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.     public TreeNode buildTree(TreeNode root, int val){
    7. 
  
  
  
  
  7.         if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
    8. 
  
  
  
  
  8.             return new TreeNode(val);
    9. 
  
  
  
  
  9.         if (root.val < val){
    10. 
  
  
  
  
  10.             root.right = buildTree(root.right, val); // 递归创建右子树
    11. 
  
  
  
  
  11.         }else if (root.val > val){
    12. 
  
  
  
  
  12.             root.left = buildTree(root.left, val); // 递归创建左子树
    13. 
  
  
  
  
  13.         }
    14. 
  
  
  
  
  14.         return root;
    15. 
  
  
  
  
  15.     }
    16. 
  
  
  
  
  16. }
    17.

Python

递归法- 有返回值

 
 
 
 
    
  
  
  
  
  1. class Solution:
    2. 
  
  
  
  
  2.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    3. 
  
  
  
  
  3.         if root is None:
    4. 
  
  
  
  
  4.             return TreeNode(val) # 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
    5. 
  
  
  
  
  5.         if root.val < val:
    6. 
  
  
  
  
  6.             root.right = self.insertIntoBST(root.right, val) # 递归创建右子树
    7. 
  
  
  
  
  7.         if root.val > val:
    8. 
  
  
  
  
  8.             root.left = self.insertIntoBST(root.left, val) # 递归创建左子树
    9. 
  
  
  
  
  9.         return root
    10.

递归法- 无返回值

 
 
 
 
    
  
  
  
  
  1. class Solution:
    2. 
  
  
  
  
  2.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    3. 
  
  
  
  
  3.         if not root:
    4. 
  
  
  
  
  4.             return TreeNode(val)
    5. 
  
  
  
  
  5.         parent = None
    6. 
  
  
  
  
  6.         def __traverse(cur: TreeNode, val: int) -> None:
    7. 
  
  
  
  
  7.             # 在函数运行的同时把新节点插入到该被插入的地方.
    8. 
  
  
  
  
  8.             nonlocal parent
    9. 
  
  
  
  
  9.             if not cur:
    10. 
  
  
  
  
  10.                 new_node = TreeNode(val)
    11. 
  
  
  
  
  11.                 if parent.val < val:
    12. 
  
  
  
  
  12.                     parent.right = new_node
    13. 
  
  
  
  
  13.                 else:
    14. 
  
  
  
  
  14.                     parent.left = new_node
    15. 
  
  
  
  
  15.                 return
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.             parent = cur # 重点: parent的作用只有运行到上面if not cur:才会发挥出来.
    18. 
  
  
  
  
  18.             if cur.val < val:
    19. 
  
  
  
  
  19.                 __traverse(cur.right, val)
    20. 
  
  
  
  
  20.             else:
    21. 
  
  
  
  
  21.                 __traverse(cur.left, val)
    22. 
  
  
  
  
  22.             return
    23. 
  
  
  
  
  23.         __traverse(root, val)
    24. 
  
  
  
  
  24.         return root
    25.

迭代法与无返回值的递归函数的思路大体一致

 
 
 
 
    
  
  
  
  
  1. class Solution:
    2. 
  
  
  
  
  2.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    3. 
  
  
  
  
  3.         if not root:
    4. 
  
  
  
  
  4.             return TreeNode(val)
    5. 
  
  
  
  
  5.         parent = None
    6. 
  
  
  
  
  6.         cur = root
    7. 
  
  
  
  
  7. 
  
  
  
  
  8.         # 用while循环不断地找新节点的parent
    9. 
  
  
  
  
  9.         while cur:
    10. 
  
  
  
  
  10.             if cur.val < val:
    11. 
  
  
  
  
  11.                 parent = cur
    12. 
  
  
  
  
  12.                 cur = cur.right
    13. 
  
  
  
  
  13.             elif cur.val > val:
    14. 
  
  
  
  
  14.                 parent = cur
    15. 
  
  
  
  
  15.                 cur = cur.left
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.         # 运行到这意味着已经跳出上面的while循环,
    18. 
  
  
  
  
  18.         # 同时意味着新节点的parent已经被找到.
    19. 
  
  
  
  
  19.         # parent已被找到, 新节点已经ready. 把两个节点黏在一起就好了.
    20. 
  
  
  
  
  20.         if parent.val > val:
    21. 
  
  
  
  
  21.             parent.left = TreeNode(val)
    22. 
  
  
  
  
  22.         else:
    23. 
  
  
  
  
  23.             parent.right = TreeNode(val)
    24. 
  
  
  
  
  24. 
  
  
  
  
  25.         return root
    26.

新闻标题：聊聊二叉搜索树中的插入操作
网页路径：http://www.shufengxianlan.com/qtweb/news49/28199.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

云服务器知识

同城分类信息

成都路面机械设备　　 　巴中倍辉科技　　 　成都网站排名　　 　UI设计　　 　手机微信网站　　 　成都网络公司　　 　成都西云机房　　 　四川艺考培训　　 　小谭建站工作室　　 　微信小程序开发　　 　铁科精智测控　　 　成都400电话　　 　成都二枢电信服务器托管　　 　成都木托盘　　 　成都网站建设公司　　 　鼎尚理发店　　 　广安园林景观设计　　 　温江电信机房　　 　移动机房服务器托管　　 　香港虚拟主机空间