Skip to content

LeetCode: 701-Insert into Binary Search Tree 解題紀錄

Last Updated on 2022-01-12 by Clay

題目

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Constraints:

  • The number of nodes in the tree will be in the range [0, 104].
  • -108 <= Node.val <= 108
  • All the values Node.val are unique.
  • -108 <= val <= 108
  • It’s guaranteed that val does not exist in the original BST.

題目給定一組二元搜索樹，以及一個要插入的值，我們要做的就是以符合二元搜索樹的規則插入新值，並回傳整棵樹。

解題思路

在將原始函式當成遞迴來解的話，就只會存在三種狀況：

  • 插入值比當前節點值還大：把右節點和插入值傳入遞迴函式
  • 插入值比當前結點值還小：把左節點和插入值傳入遞迴函式
  • 當前節點不存在：建立新的節點，值即為插入值

在節點存在的情況，比方說右節點存在而我們要繼續遞迴，別忘了在程式中將新的遞迴函式回傳新的右節點底下的樹結構。詳細情況可以參考下方程式碼。


C++ 範例程式碼

/**
 * Definition for a binary tree node.
 * 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 *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // Base case
        if (root == nullptr) {
            return new TreeNode(val);
        }
        if (val > root->val) {
            root->right = insertIntoBST(root->right, val);
        }
        else if (val < root->val) {
            root->left = insertIntoBST(root->left, val);
        }
    
        return root;
    }
};



Python 範例程式碼

# Definition for a binary tree node.
# 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]:
        # Base case
        if not root: return TreeNode(val)
        elif val > root.val: root.right = self.insertIntoBST(root.right, val)
        else: root.left = self.insertIntoBST(root.left, val)
            
        return root

References

Read More

Tags:

Leave a Reply