701. Insert into a Binary Search Tree

Loading...LeetCode

Note 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.

因为题目是返回任意有效解即可，那直接找最简单的解法：把 val 放在叶子节点，这样其实就不是 insert 了，只是把新 node 添加到 tree 最末。这样的话就是利用BST的性质一路DFS找合法位置。

不知道为什么，先做right要比先做left快很多，也不知道是leetcode cases太不平衡了还是有什么玄机。

01/18/2021 Update:

recursive 的写法需要额外栈空间，可能会导致溢出，多写一个 iterative 的写法。

recursive

# 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: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        
        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
        
        return root

iterative

# 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: TreeNode, val: int) -> TreeNode:
        if not root: return TreeNode(val)
        curr = root
        while curr:
            if curr.val > val:
                if not curr.left:
                    curr.left = TreeNode(val)
                    break
                else:
                    curr = curr.left
            else:
                if not curr.right:
                    curr.right = TreeNode(val)
                    break
                else:
                    curr = curr.right
        return root