2020-2-18 刷题记录

0X00 leetcode 做了 6 道

• LeetCode 700. Search in a Binary Search Tree

• LeetCode 99. Recover Binary Search Tree

• LeetCode 108. Convert Sorted Array to Binary Search Tree

• LeetCode 668. Kth Smallest Number in Multiplication Table

• LeetCode 378. Kth Smallest Element in a Sorted Matrix

• LeetCode 98. Validate Binary Search Tree

0X01 每道题的小小总结

700 Search in a Binary Search Tree

水..为了凑齐今天总题目增加 5 道

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if root is None: return None
        if root.val == val: return root
        elif root.val > val: return self.searchBST(root.left, val)
        return self.searchBST(root.right, val)

LeetCode 99. Recover Binary Search Tree

中序遍历的一道题目

树的中序遍历是有序的

在中序遍历的过程中一旦发现不是有序的就标记成未来可能要交换的这里非常重要!

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.first = self.second = self.pre = None

        def inorder(root):
            if root is None:return
            inorder(root.left)
            if self.pre != None and self.pre.val > root.val:
                if self.first is None: self.first = self.pre
                self.second = root
            self.pre = root
            inorder(root.right)
        inorder(root)
        self.first.val, self.second.val = self.second.val, self.first.val

LeetCode 108. Convert Sorted Array to Binary Search Tree

这道题非常的经典(花花说的)

做到这一点很简单...只要让左右子树的元素数量差值小于等于 1 就行

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def build(start, end):
            if start > end: return
            mid = start + (end - start) // 2
            root = TreeNode(nums[mid])
            root.left = build(start, mid - 1)
            root.right = build(mid + 1, end)
            return root
        
        return build(0, len(nums)-1)

668 Kth Smallest Number in Multiplication Table

hard 题总结在上篇博客

378 Kth Smallest Element in a Sorted Matrix

中等题,总结在上篇博客

98 Validate Binary Search Tree

中序遍历的一道题..

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # 中序遍历
        # 判断前元素是不是小于当前元素

        cur, pre = root, float("-inf")
        stack = []

        while len(stack) > 0 or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            if node.val <= pre:
                return False
            
            cur = node.right
            pre = node.val
        
        return T