美文网首页
Leetcode_669_修剪二叉搜索树_hn

Leetcode_669_修剪二叉搜索树_hn

作者: 1只特立独行的猪 | 来源:发表于2020-03-13 20:14 被阅读0次

    题目描述

    给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。

    示例

    示例 1:

    输入: 
        1
       / \
      0   2
    
      L = 1
      R = 2
    
    输出: 
        1
          \
           2
    

    示例2

    输入: 
        3
       / \
      0   4
       \
        2
       /
      1
    
      L = 1
      R = 3
    
    输出: 
          3
         / 
       2   
      /
     1
    

    解答方法

    方法一:

    思路

    二叉搜索树:*节点值大于它的左节点并且小于它的右节点
    那么:

    • 当节点值 < L ,把它的左子树抛弃掉,继续修剪它的右子树
    • 当节点值 > R ,把它的右子树抛弃掉,继续修剪它的左子树
    • 当前节点值满足 L < node.val < R ,那么它的左右子树都有可能仍然有符合条件的节点值,所以要继续修剪左、右子树

    代码

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
            if root is None:
                return None
            if root.val < L:
                return self.trimBST(root.right, L, R)
            if root.val > R:
                return self.trimBST(root.left, L, R)
            root.left = self.trimBST(root.left, L, R)
            root.right = self.trimBST(root.right, L, R)
            return root
    

    时间复杂度

    O(n),其中 n 是给定的树的全部节点。我们最多访问每个节点一次。

    空间复杂度

    O(n),即使我们没有明确使用任何额外的内存,在最糟糕的情况下,我们递归调用的栈可能与节点数一样大。

    相关文章

      网友评论

          本文标题:Leetcode_669_修剪二叉搜索树_hn

          本文链接:https://www.haomeiwen.com/subject/ssfyshtx.html