如何在二叉搜索树中查找和插入一个节点？

简化版

查找：从根开始，目标值比当前节点小就往左走、大就往右走、相等就找到了，走到 null 说明不存在。插入：先按查找的路径往下走，走到第一个空位置（null）就把新节点挂在那里。两者都利用 BST「左小右大」的有序性，平均 O(log n)（树平衡时）。

详细版

查找

TreeNode search(TreeNode root, int target) {
    while (root != null) {
        if (target == root.val) return root;      // 命中
        root = (target < root.val) ? root.left    // 小 → 左
                                   : root.right;   // 大 → 右
    }
    return null;                                   // 到底没找到
}

每比较一次就排除一整棵子树，路径长度就是树的高度。

插入

TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);    // 找到空位，新建节点
    if (val < root.val)      root.left  = insert(root.left,  val);
    else if (val > root.val) root.right = insert(root.right, val);
    // val == root.val：值已存在，通常不重复插入
    return root;
}

插入总是发生在叶子位置：沿查找路径下降，遇到 null 就把新节点接上去。插入不会改变已有节点的位置，只在末端加一个。

完整版教学

一、查找：把有序性用到极致

BST 查找和有序数组的二分查找是同一思想：每一步都排除掉一半的可能。当前节点相当于「中间值」，目标比它小就只可能在左子树、比它大就只可能在右子树。所以查找路径就是一条从根到目标的下降路径，长度不超过树高 h。

树平衡时 h ≈ log n，查找 O(log n)。
树退化成链时 h = n，查找 O(n)。

这也说明 BST 的效率完全取决于树高，而树高取决于是否平衡。

二、插入：只在叶子处发生

插入的关键认识是：新节点一定成为某个叶子。因为我们沿着「该往哪走」的路径一直下降，直到遇到一个空位置（该方向没有孩子），把新节点挂在那儿即可。这样插入不破坏 BST 的有序性——新值走到的位置，天然满足「比沿途左拐的祖先大、比右拐的祖先小」。

递归写法里 root.left = insert(root.left, val) 的意义是：把「插入后的子树根」接回父节点。因为除了新建的叶子，其它节点位置不变，接回来的还是原来的子树根。

三、插入顺序决定树的形状

同一批数据，插入顺序不同，长出的 BST 形状完全不同：

插入 4,2,6,1,3,5,7 → 比较平衡        插入 1,2,3,4,5 → 退化成右斜链
        4                               1
       / \                               \
      2   6                               2
     /|   |\                               \
    1 3   5 7                               3 ...

有序插入是最坏情况（退化成链，O(n)）。这解释了为什么工程上要用自平衡 BST（红黑树等）——它们在插入时自动旋转，避免退化。

四、迭代 vs 递归

查找：迭代写法（循环下降）更简洁、无递归栈开销，推荐。
插入：递归写法直观（自然处理「接回子树」）；也可迭代——记录父节点，找到空位后判断挂左还是挂右。两者复杂度相同。

五、复杂度

时间：查找、插入都是 O(h)。平衡时 O(log n)，最坏 O(n)。
空间：迭代查找 O(1)；递归插入 O(h) 栈空间。

六、常见误区与追问

考点	正确口径
查找	每层根据大小只走左或右
插入	找到空位置后作为叶子挂上
风险	插入顺序可能导致退化

while cur != null:
  if val < cur.val: cur = cur.left
  else if val > cur.val: cur = cur.right
  else: found

BST 查找和插入的共同点是“沿一条搜索路径走到底”，不会同时搜索两边。

误区：插入节点可以放在任意空孩子位置。 必须沿 BST 比较路径找到唯一空位，否则会破坏左小右大的全局顺序。
误区：查找失败就说明树为空。 查找失败只是搜索路径走到空指针，树可能非空但不包含该值。
误区：递归和迭代复杂度不同。 两者走的是同一条路径，时间都是 O(h)，区别主要在代码形式和栈空间。
追问：遇到重复值怎么插入？ 常见面试默认不插入重复值；若允许重复，要先约定放左、放右或记录计数。
追问：插入为什么通常发生在叶子位置？ 沿比较路径直到空孩子才不会挤掉已有子树，也能保持 BST 性质。
追问：最坏复杂度是什么？ 树退化成链表时 h=n，查找和插入都可能是 O(n)。

七、加强记忆

BST 查找：从根开始，小往左、大往右、相等命中，到 null 即不存在，O(h)。插入：沿查找路径下降到第一个空位，把新节点挂上去——插入总在叶子处、不改动已有节点，也不破坏有序性。效率取决于树高：平衡 O(log n)、退化成链 O(n)。有序插入是最坏情况，故工程用自平衡 BST。

简化版

详细版

查找

插入