插入二叉搜索树

# -*- coding: utf-8 -*-


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class BT:
    def __init__(self):
        self.root = None

    def levelOrderToBT(self, nums):
        n = len(nums)

        if n > 0:
            self.root = TreeNode(nums[0])
            queue, idx = [self.root], 1

            while queue and idx < n:
                node = queue.pop(0)
                node.left = TreeNode(nums[idx]) \
                    if nums[idx] != None else None
                if node.left:
                    queue.append(node.left)
                node.right = TreeNode(nums[idx + 1]) \
                    if idx + 1 < n and nums[idx + 1] != None else None
                if node.right:
                    queue.append(node.right)
                idx += 2

        return self.root

    @staticmethod
    def levelOrder(root):
        if not root:
            return []

        res, queue = [], [root]
        while queue:
            node = queue.pop(0)
            if node:
                res.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append(None)

        while res and res[-1] == None:
            res.pop()

        return res


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @param val int整型
# @return TreeNode类
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/4900db9ddfbd43a7a9841c6a408bacf2?tpId=196&tqId=40503&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        搜索二叉树的插入，使用双指针parent、cur分别指向待插入位置的父节点和待插入位置，从根节点开始遍历二叉树，寻找插入位置
    复杂度：
        时间复杂度：O(logN)
        空间复杂度：O(1)
    """

    def insertToBST(self, root, val):
        # write code here
        if not root:
            return TreeNode(val)
        parent, cur = None, root
        while cur:
            if cur.val == val:
                return root
            elif cur.val < val:  # 插入右子树
                parent, cur = cur, cur.right
            else:  # 插入左子树
                parent, cur = cur, cur.left
        if parent.val > val:
            parent.left = TreeNode(val)
        elif parent.val < val:
            parent.right = TreeNode(val)
        return root


if __name__ == "__main__":
    sol = Solution()

    nums, val = [2, 1, 3], 4

    bt = BT()
    bt1 = bt.levelOrderToBT(nums)
    print BT.levelOrder(bt1)

    res = sol.insertToBST(bt1, val)
    print BT.levelOrder(res)