# LeetCode Medium 701. Insert into a Binary Search Tree

tags: leetcode

問題

• Explore
• Problems

実際のコーディングテストでPython3を使うことが多いことから，Python3で書くことに…

発言に一貫性がないという点で自分は一貫性がある？

アイデア

BSTに新たな値を挿入しろという問題です．

その値はBST内に存在しないという仮定があり，複数の解が想定できる場合はそのどれでも良いです．

これは，BSTの定義通りにやるだけですね．

解法1(recursive)

BSTの定義に合わせて

• valが現在のノードのvalよりも小さいとき
  • 左部分木に挿入する可能性がある．
  • 左木がなければ新しくノードを作る
  • あれば，再帰的に探索する
• そうでないとき(つまり，valが現在のノードよりも大きいとき)
  • 左部分木に挿入する可能性がある．
  • 左木がなければ新しくノードを作る
  • あれば，再帰的に探索する
• そして，rootを返せば良いです．

計算量

ノードの数を$N$，木の高さを$H$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(H)$

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if val < root.val:
            if not root.left:
                root.left = TreeNode(val)
            else:
                self.insertIntoBST(root.left, val)
        else:
            if not root.right:
                root.right = TreeNode(val)
            else:
                self.insertIntoBST(root.right, val)
        return root