给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和 插入的值: 5
你可以返回这个二叉搜索树:
4
/ \
2 7
/ \ /
1 3 5
或者这个树也是有效的:
5
/ \
2 7
/ \
1 3
\
4
思路一:
根据二叉搜索树的性质,利用递归找到一个可以插入的位置就好啦。
时间复杂度:O(N)
空间复杂度:O(N)
class Solution(object):
def insertIntoBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if not root:
return
def helper(node, val):
if node.val < val:
if not node.right:
node.right = TreeNode(val)
else:
helper(node.right, val)
elif node.val > val:
if not node.left:
node.left = TreeNode(val)
else:
helper(node.left, val)
helper(root, val)
return root
以下写于2020年01月08日20:39:55:
class Solution(object):
def insertIntoBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: 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
第二种思路:
迭代,还是利用二叉搜索树的性质,找到插入后节点的父节点。
时间复杂度:O(N)
空间复杂度:O(1)
class Solution(object):
def insertIntoBST(self, root, val):
if not root:
return TreeNode(val)
node, parent = root, root
while node:
parent = node
node = parent.left if val < parent.val else parent.right
if val > parent.val:
parent.right = TreeNode(val)
else:
parent.left = TreeNode(val)
return root
版权声明:本文为qq_32424059原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。