给定一棵二叉搜索树的根节点和一个插入值 val。请你把这个 val 插入二叉搜索树中并保持这棵树依然是二叉搜索树。你可以返回任意一个合法结果。
例如:输入二叉树,插入一个 4 ,可能的结果有,等等,返回任意一个即可。
数据范围:二叉搜索树节点数满足 ,二叉搜索树上节点值满足
# -*- 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)