leetcode_701. 二叉搜索树中的插入操作
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
...
目录
一、题目内容
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
给定二叉搜索树:
4
/ \
2 7
/ \
1 3和 插入的值: 5
你可以返回这个二叉搜索树:4
/ \
2 7
/ \ /
1 3 5
或者这个树也是有效的:5
/ \
2 7
/ \
1 3
\
4
提示:
给定的树上的节点数介于 0 和 10^4 之间
每个节点都有一个唯一整数值,取值范围从 0 到 10^8
-10^8 <= val <= 10^8
新值和原始二叉搜索树中的任意节点值都不同
二、解题思路
根据BST的性质,左小右大,因此递归的判断,直到对应子节点为空就插入。
三、代码
-
-
# 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
-
-
def __repr__(self):
-
return str(self.val)
-
-
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
-
-
-
if __name__ == '__main__':
-
a = TreeNode(4)
-
a.left = TreeNode(2)
-
a.right = TreeNode(7)
-
a.left.left = TreeNode(1)
-
a.left.right = TreeNode(3)
-
-
s = Solution()
-
val = 5
-
ans = s.insertIntoBST(a, val)
-
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/108882660
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)