LeetCode 701. 二叉搜索树中的插入操作

题目

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证 ,新值和原始二叉搜索树中的任意节点值都不同。注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

例:
输入:root = [4,2,7,1,3], val = 5

输出:[4,2,7,1,3,5]
解释:另一个满足题目要求可以通过的树是:

方法:递归
  • 若为空树(或节点的左孩子,或节点的右孩子为空),即表示此处为插入值的位置,那么返回插入的节点
  • 若插入值小于此时的节点值,即表示插入的位置在该节点的左部,那么调用 insertIntoBST 函数继续遍历
  • 若插入值大于此时的节点值,即表示插入的位置在该节点的右部,那么调用 insertIntoBST 函数继续遍历
  • 最终返回插入后的根节点
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def insertIntoBST(self, root, val):
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)
        return root
参考

代码相关:https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容