二叉树——17.二叉搜索树中的插入操作

本文主要是介绍二叉树——17.二叉搜索树中的插入操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣题目链接

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

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

解题思路

1. 理解二叉搜索树（BST）的性质

首先，需要理解二叉搜索树的基本性质：

对于每个节点，左子树中所有节点的值都小于该节点的值。
右子树中所有节点的值都大于该节点的值。
因此，插入一个新值时，需要遵循这个规则，找到适合的位置。

2. 递归遍历寻找插入位置

为了找到新节点的插入位置，采用递归遍历树的方式：

从根节点开始，比较当前节点的值与要插入的值。
- 如果插入值小于当前节点的值，则进入左子树继续寻找。
- 如果插入值大于当前节点的值，则进入右子树继续寻找。
当找到一个空的子节点（即当前节点的子节点为 None）时，说明这是合适的插入位置。

3. 插入新节点

在递归遍历过程中，保持对当前节点的父节点的引用（parent）。当找到合适的插入位置时，根据插入值与父节点的比较结果，将新节点插入为父节点的左子节点或右子节点。

4. 处理特殊情况

在树为空的情况下，直接将新节点作为根节点返回。

5. 总体解题思路总结

利用递归来遍历树，直到找到合适的插入位置。
通过保持对父节点的引用，确保新节点可以正确地插入到树中。
特殊情况下，直接处理空树并返回新的根节点。

这个思路的核心是利用二叉搜索树的性质和递归的思想，以保证插入操作符合 BST 的规则。

完整代码如下：

class Solution:def __init__(self):self.parent = Nonedef traversal(self, cur, val):if cur is None:node = TreeNode(val)if val > self.parent.val:self.parent.right = nodeelse:self.parent.left = nodereturnself.parent = curif cur.val > val:self.traversal(cur.left, val)if cur.val < val:self.traversal(cur.right, val)def insertIntoBST(self, root, val):self.parent = TreeNode(0)if root is None:return TreeNode(val)self.traversal(root, val)return root

def traversal(self, cur, val):if cur is None:node = TreeNode(val)if val > self.parent.val:self.parent.right = nodeelse:self.parent.left = nodereturnself.parent = curif cur.val > val:self.traversal(cur.left, val)if cur.val < val:self.traversal(cur.right, val)

基准条件判断：
- 如果 cur 是 None，说明我们已经找到适合插入的位置。此时：
  - 创建一个新的 TreeNode，其值为 val。
  - 根据 val 与 self.parent.val 的比较结果，将新节点插入为 self.parent 的左子节点或右子节点。
  - 然后返回结束递归。
递归遍历：
- 在未找到插入位置时，继续沿着树遍历：
  - 当前节点的值 (cur.val) 大于 val 时，递归遍历当前节点的左子树。
  - 当前节点的值 (cur.val) 小于 val 时，递归遍历当前节点的右子树。
- 在递归前更新 self.parent 为当前节点 cur，以便跟踪新节点的父节点。

def insertIntoBST(self, root, val):self.parent = TreeNode(0)if root is None:return TreeNode(val)self.traversal(root, val)return root

初始化父节点：
- 在执行插入操作前，将 self.parent 初始化为一个新的节点（值为0）。这个初始化操作主要为了处理边界情况，确保在整个插入过程中 parent 有合理的值。
特殊情况处理：
- 如果树为空（root 为 None），直接返回一个新的节点作为根节点。
调用 traversal 方法：
- 否则，调用 traversal 方法，从根节点开始遍历，找到适合插入的位置并插入新节点。
返回根节点：
- 最后，返回操作后的树的根节点。