二叉搜索树中的插入操作 图解题解

这道题到底在问什么

输入

root=[40,20,60,10,30,50,70], val=25

输出

25 挂在 30 的左孩子(叶子插入法)

输入

root=[], val=5

输出

[5](新建根)

最优解：一步一步想明白

1. 3记住「小往左、大往右,走到空位就新建叶子挂上」,下面逐帧套它。新节点一定是作为叶子插入,不会改动已有节点的连接。
2. 4插入值 val = 25先看这棵 BST:根 40,左边 20(挂着 10、30)、右边 60(挂着 50、70)。要插入的值是 25,我们从根开始一路比较着往下找它该待的空位。
3. 5插入值 val = 25先找感觉:BST 里每个节点左边整棵都比它小、右边整棵都比它大。按叶子插入法,拿 25 和路上的节点一路比较,小就向左、大就向右,这条下行路线就被有序性钉死了,最后会走到一个空孩子。
4. 6插入值 val = 25第一拍,当前停在根 40,先把要插入的 25 和 40 比一比,问一句:25 比 40 小吗?
5. 7插入值 val = 25答案是成立的,25 确实比 40 小。按「小往左」的规矩,下一步就走进 40 的左子树。
6. 8插入值 val = 25顺着左边来到 20,这是第二拍。还是同样动作,把 25 和 20 比一比,问:25 比 20 小吗?
7. 9插入值 val = 25这回不成立,25 不比 20 小,反而 25 > 20。那就按「大往右」,下一步走进 20 的右子树。
8. 10插入值 val = 25走到 20 的右孩子 30,第三拍。继续比,把 25 和 30 放一起:25 比 30 小吗?
9. 11插入值 val = 25成立,25 比 30 小,该往 30 的左边走。可是看一眼 30 的左孩子,它是空的。一路比下来终于撞到了空位,这就是叶子插入法这条下行路线对应的落点。
10. 12插入值 val = 25在这个空位新建一个值为 25 的节点,标成绿色,把它接到 30 的左孩子位置。25 作为一片新叶子长了出来,没有动到任何已有节点的连接。
11. 13插入值 val = 25插入完成。25 现在是 30 的左孩子,中序遍历变成 10,20,25,30,40,50,60,70,严格升序,整棵树依旧满足「左小右大」,还是一棵合法的 BST,25 正好落在它该在的 20 和 30 之间。
12. 14插入值 val = 25回头看 25 这一趟:从 40 到 20 到 30,最后落到 30 左边的空位。规律就一句话,小往左、大往右,走到空位就新建叶子挂上。下面换个值,把这条规律再走一遍。
13. 15插入值 val = 65这次要插入的值是 65,我们重新回到根 40。规则一点没变,还是小往左、大往右,看看 65 会走出一条完全不同的路。
14. 16插入值 val = 65先停在根 40,把 65 和 40 比一比,问一句:65 比 40 小吗?
15. 17插入值 val = 65不成立,65 不比 40 小,反而 65 > 40。按「大往右」,下一步走进 40 的右子树,和刚才 25 往左正好相反。
16. 18插入值 val = 65顺着右边来到 60。继续比,65 > 60,还是比它大,继续往右,走进 60 的右子树。
17. 19插入值 val = 65走到 60 的右孩子 70。再比一次,这回问:65 比 70 小吗?
18. 20插入值 val = 65成立,65 比 70 小,该往 70 的左边走。看一眼 70 的左孩子,又是空的。空位找到了,65 就该挂在这里。
19. 21插入值 val = 65在 70 的左孩子位置新建一个值为 65 的节点,标绿挂上。65 同样是作为一片新叶子长出来的,没有动任何已有连接。
20. 22插入值 val = 65两次插入都完成了。现在中序遍历是 10,20,25,30,40,50,60,65,70,依旧严格升序,25 和 65 各自落在自己该在的位置,整棵树仍是合法 BST。
21. 23插入值 val = 65回头看这两趟:25 走的是左半边、65 走的是右半边,可用的规则一模一样。从根出发,val 比当前小就往左、比当前大就往右,一路下行直到某一侧是空,就在那个空位新建叶子挂上。BST 的有序性钉死了这条下行路线,一趟 O(h) 就插好了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root: return TreeNode(val)
        if val < root.val: root.left = self.insertIntoBST(root.left, val)
        else: root.right = self.insertIntoBST(root.right, val)
        return root

#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: TreeNode* insertIntoBST(TreeNode* root,int val){ if(!root)return new TreeNode(val); if(val<root->val)root->left=insertIntoBST(root->left,val); else root->right=insertIntoBST(root->right,val); return root; }};

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public TreeNode insertIntoBST(TreeNode root,int val){ if(root==null)return new TreeNode(val); if(val<root.val)root.left=insertIntoBST(root.left,val); else root.right=insertIntoBST(root.right,val); return root; } }

复杂度

面试官可能追问