[[421164]]

二叉搜索樹中的插入操作

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

給定二叉搜索樹(BST)的根節點和要插入樹中的值，將值插入二叉搜索樹。返回插入后二叉搜索樹的根節點。輸入數據保證，新值和原始二叉搜索樹中的任意節點值都不同。

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

提示：

• 給定的樹上的節點數介于 0 和 10^4 之間
• 每個節點都有一個唯一整數值，取值范圍從 0 到 10^8
• -10^8 <= val <= 10^8
• 新值和原始二叉搜索樹中的任意節點值都不同

思路

其實這道題目其實是一道簡單題目，但是題目中的提示：有多種有效的插入方式，還可以重構二叉搜索樹，一下子嚇退了不少人，瞬間感覺題目復雜了很多。

其實可以不考慮題目中提示所說的改變樹的結構的插入方式。

如下演示視頻中可以看出：只要按照二叉搜索樹的規則去遍歷，遇到空節點就插入節點就可以了。

二叉搜索樹中的插入操作

例如插入元素10 ，需要找到末尾節點插入便可，一樣的道理來插入元素15，插入元素0，插入元素6，需要調整二叉樹的結構么?并不需要。。

只要遍歷二叉搜索樹，找到空節點 插入元素就可以了，那么這道題其實就簡單了。

接下來就是遍歷二叉搜索樹的過程了。

遞歸

遞歸三部曲：

• 確定遞歸函數參數以及返回值

參數就是根節點指針，以及要插入元素，這里遞歸函數要不要有返回值呢?

可以有，也可以沒有，但遞歸函數如果沒有返回值的話，實現是比較麻煩的，下面也會給出其具體實現代碼。

有返回值的話，可以利用返回值完成新加入的節點與其父節點的賦值操作。(下面會進一步解釋)

遞歸函數的返回類型為節點類型TreeNode * 。

代碼如下：

TreeNode* insertIntoBST(TreeNode* root, int val) 

• 確定終止條件

終止條件就是找到遍歷的節點為null的時候，就是要插入節點的位置了，并把插入的節點返回。

代碼如下：

if (root == NULL) { 
    TreeNode* node = new TreeNode(val); 
    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將其接住。

整體代碼如下：

class Solution { 
public: 
    TreeNode* insertIntoBST(TreeNode* root, int val) { 
        if (root == NULL) { 
            TreeNode* node = new TreeNode(val); 
            return node; 
        } 
        if (root->val > val) root->left = insertIntoBST(root->left, val); 
        if (root->val < val) root->right = insertIntoBST(root->right, val); 
        return root; 
    } 
}; 

可以看出代碼并不復雜。

剛剛說了遞歸函數不用返回值也可以，找到插入的節點位置，直接讓其父節點指向插入節點，結束遞歸，也是可以的。

那么遞歸函數定義如下：

TreeNode* parent; // 記錄遍歷節點的父節點 
void traversal(TreeNode* cur, int val) 

沒有返回值，需要記錄上一個節點(parent)，遇到空節點了，就讓parent左孩子或者右孩子指向新插入的節點。然后結束遞歸。

代碼如下：

class Solution { 
private: 
    TreeNode* parent; 
    void traversal(TreeNode* cur, int val) { 
        if (cur == NULL) { 
            TreeNode* node = new TreeNode(val); 
            if (val > parent->val) parent->right = node; 
            else parent->left = node; 
            return; 
        } 
        parent = cur; 
        if (cur->val > val) traversal(cur->left, val); 
        if (cur->val < val) traversal(cur->right, val); 
        return; 
    } 
 
public: 
    TreeNode* insertIntoBST(TreeNode* root, int val) { 
        parent = new TreeNode(0); 
        if (root == NULL) { 
            root = new TreeNode(val); 
        } 
        traversal(root, val); 
        return root; 
    } 
}; 

可以看出還是麻煩一些的。

我之所以舉這個例子，是想說明通過遞歸函數的返回值完成父子節點的賦值是可以帶來便利的。

網上千變一律的代碼，可能會誤導大家認為通過遞歸函數返回節點 這樣的寫法是天經地義，其實這里是有優化的!

迭代

再來看看迭代法，對二叉搜索樹迭代寫法不熟悉，可以看這篇：二叉樹：二叉搜索樹登場!

在迭代法遍歷的過程中，需要記錄一下當前遍歷的節點的父節點，這樣才能做插入節點的操作。

在530.二叉搜索樹的最小絕對差和501.二叉搜索樹中的眾數中，都是用了記錄pre和cur兩個指針的技巧，本題也是一樣的。

代碼如下：

class Solution { 
public: 
    TreeNode* insertIntoBST(TreeNode* root, int val) { 
        if (root == NULL) { 
            TreeNode* node = new TreeNode(val); 
            return node; 
        } 
        TreeNode* cur = root; 
        TreeNode* parent = root; // 這個很重要，需要記錄上一個節點，否則無法賦值新節點 
        while (cur != NULL) { 
            parent = cur; 
            if (cur->val > val) cur = cur->left; 
            else cur = cur->right; 
        } 
        TreeNode* node = new TreeNode(val); 
        if (val < parent->val) parent->left = node;// 此時是用parent節點的進行賦值 
        else parent->right = node; 
        return root; 
    } 
}; 

總結

首先在二叉搜索樹中的插入操作，大家不用恐懼其重構搜索樹，其實根本不用重構。

然后在遞歸中，我們重點講了如果通過遞歸函數的返回值完成新加入節點和其父節點的賦值操作，并強調了搜索樹的有序性。

最后依然給出了迭代的方法，迭代的方法就需要記錄當前遍歷節點的父節點了，這個和沒有返回值的遞歸函數實現的代碼邏輯是一樣的。

其他語言版本

Java

class Solution { 
    public TreeNode insertIntoBST(TreeNode root, int val) { 
        if (root == null) return new TreeNode(val); 
        TreeNode newRoot = root; 
        TreeNode pre = root; 
        while (root != null) { 
            pre = root; 
            if (root.val > val) { 
                root = root.left; 
            } else if (root.val < val) { 
                root = root.right; 
            } 
        } 
        if (pre.val > val) { 
            pre.left = new TreeNode(val); 
        } else { 
            pre.right = new TreeNode(val); 
        } 
 
        return newRoot; 
    } 
} 

遞歸法

class Solution { 
    public TreeNode insertIntoBST(TreeNode root, int val) { 
        return buildTree(root, val); 
    } 
 
    public TreeNode buildTree(TreeNode root, int val){ 
        if (root == null) // 如果當前節點為空，也就意味著val找到了合適的位置，此時創建節點直接返回。 
            return new TreeNode(val); 
        if (root.val < val){ 
            root.right = buildTree(root.right, val); // 遞歸創建右子樹 
        }else if (root.val > val){ 
            root.left = buildTree(root.left, val); // 遞歸創建左子樹 
        } 
        return root; 
    } 
} 

Python

遞歸法 - 有返回值

class Solution: 
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode: 
        if root is None: 
            return TreeNode(val) # 如果當前節點為空，也就意味著val找到了合適的位置，此時創建節點直接返回。 
        if root.val < val: 
            root.right = self.insertIntoBST(root.right, val) # 遞歸創建右子樹 
        if root.val > val: 
            root.left = self.insertIntoBST(root.left, val) # 遞歸創建左子樹 
        return root 

遞歸法 - 無返回值

class Solution: 
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode: 
        if not root: 
            return TreeNode(val) 
        parent = None 
        def __traverse(cur: TreeNode, val: int) -> None: 
            # 在函數運行的同時把新節點插入到該被插入的地方. 
            nonlocal parent 
            if not cur: 
                new_node = TreeNode(val) 
                if parent.val < val: 
                    parent.right = new_node 
                else: 
                    parent.left = new_node 
                return 
 
            parent = cur # 重點: parent的作用只有運行到上面if not cur:才會發揮出來. 
            if cur.val < val: 
                __traverse(cur.right, val) 
            else: 
                __traverse(cur.left, val) 
            return 
        __traverse(root, val) 
        return root 

迭代法與無返回值的遞歸函數的思路大體一致

class Solution: 
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode: 
        if not root: 
            return TreeNode(val) 
        parent = None 
        cur = root 
 
        # 用while循環不斷地找新節點的parent 
        while cur: 
            if cur.val < val: 
                parent = cur 
                cur = cur.right 
            elif cur.val > val: 
                parent = cur 
                cur = cur.left 
 
        # 運行到這意味著已經跳出上面的while循環, 
        # 同時意味著新節點的parent已經被找到. 
        # parent已被找到, 新節點已經ready. 把兩個節點黏在一起就好了. 
        if parent.val > val: 
            parent.left = TreeNode(val) 
        else: 
            parent.right = TreeNode(val) 
 
        return root