LeetCode-665. 非递减数列 and LeetCode-669. 修剪二叉搜索树

LeetCode-665

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。

示例 1:

输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
说明:  n 的范围为 [1, 10,000]。

solution:

class Solution:def checkPossibility(self, nums: List[int]) -> bool:if len(nums) == 1:return Truetype1 = 1for i in range(1,len(nums)):if i+1 < len(nums):if nums[i-1] > nums[i]:type1-=1if nums[i-1] > nums[i+1]:if i !=1:if nums[i-2] > nums[i]:return Falseelif i == len(nums)-1:type1-= 1 if nums[i-1] > nums[i] else 0 return True if type1 >=0 else False

LeetCode-669

给定一个二叉搜索树，同时给定最小边界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

渣渣的solution就硬模拟...不过速度还可以击败百分之98的用户..

solution:

class Solution:def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:      nrange = range(L,R+1)que = []que.append(root)if len(que) == 0:return Nonehead = rootp = headfirst = 1while len(que) !=0:q = que[0]if q.val in nrange:if first == 1:head = qp = headfirst = 0else:p = qif q.right!=None:if q.right.val in nrange:if first==1:head = q.rightp = headfirst = 0else: p.right = q.rightque.append(q.right)else:node = q.rightif node.left == None:p.right = Nonefind = 0while node!=None:if node.left==None:breakelse:if node.left.val in nrange:find = 1p.right = node.leftque.append(node.left)breakelse:node = node.leftif find == 0:p.right = Noneif q.left!=None:if q.left.val in nrange:if first==1:head = q.leftp = headfirst = 0else: p.left = q.leftque.append(q.left)else:node = q.leftif node.right == None:p.left = Nonefind = 0while node!=None:if node.right==None:breakelse:if node.right.val in nrange:find = 1p.left = node.rightque.append(node.right)breakelse:node = node.rightif find == 0:p.left = Noneelif q.val not in nrange:if q.val < nrange[0]:if q.right!=None:que.append(q.right)else:if q.left!=None:que.append(q.left)que.pop(0)return head

官方题解。。。：

class Solution(object):def trimBST(self, root, L, R):def trim(node):if not node:return Noneelif node.val > R:return trim(node.left)elif node.val < L:return trim(node.right)else:node.left = trim(node.left)node.right = trim(node.right)return nodereturn trim(root)作者：LeetCode
链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree/solution/xiu-jian-er-cha-sou-suo-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！