Leetcode Daily Practice
Share
Explore

# ⁠98. Validate Binary Search Tree⁠⁠

class Solution:
def isValidBST(self, root: TreeNode) -> bool:

## 1. Recursion

Design a new helper function to help iterate left to right:
def helper(node, lower = float('-inf'), upper = float('inf')):
#‘inf’ means the infinite value
Approach:
As long as the left sub-tree is not None, and all the node.val in the left sub-tree is less than the root.val; if the right sub-tree is not none, then all the node.val in the right is bigger than the root.val.
`class Solution:`` def isValidBST(self, root):`` """`` :type root: TreeNode`` :rtype: bool`` """`` def helper(node, lower = float('-inf'), upper = float('inf')):`` if not node:`` return True`` `` val = node.val`` if val <= lower or val >= upper:`` return False`
` if not helper(node.right, val, upper):`` return False`` if not helper(node.left, lower, val):`` return False`` return True`
` return helper(root)`

## 2. In-order traversal

Approach:
Use a stack to store the nodes
`class Solution:`` def isValidBST(self, root):`` """`` :type root: TreeNode`` :rtype: bool`` """`` stack, inorder = [], float('-inf')`` `` while stack or root:`` while root:`` stack.append(root)`` root = root.left`` root = stack.pop()`` # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树`` if root.val <= inorder:`` return False`` inorder = root.val`` root = root.right`
` return True`

# ⁠32. Longest Valid Parentheses⁠⁠

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
`Input: "(()"``Output: 2``Explanation: The longest valid parentheses substring is "()"`
Example 2:
`Input: ")()())"``Output: 4``Explanation: The longest valid parentheses substring is "()()"`

## 1. DP

1. if s ended with ‘(’
return 0
2. if s ended with ‘)’
2.1 if s[i-1] == ‘)’ : s[i-1 - dp[i-1]]
2.2 if s[i-1] == ')' and s[i-1-dp[i-1]] == '(' and i-1-dp[i-1]>=0:
`def longestValidParentheses(self, s: str) -> int:`` # 状态：以该点结尾的最长有效括号的子串长度`` dp = [0 for _ in range(len(s))]`` if len(s) < 2:`` return 0`` if s[1] == ')' and s[0] == '(':`` dp[1] = 2`` `` if len(s) == 2:`` return dp[1]`
` for i in range(2, len(s)):`` if s[i] == '(': ## 一种情况`` dp[i] = 0`` continue`` if s[i] == ')': ## 另一种情况`` if s[i-1] == '(': ## 细分`` dp[i] = dp[i-2] +2`` if s[i-1] == ')' and s[i-1-dp[i-1]] == '(' and i-1-dp[i-1]>=0: ## only for python`` dp[i] = dp[i-1-dp[i-1]-1] + 2 + dp[i-1]`` print(dp) `` return max(dp)`
2. Stack
`def longestValidParentheses(self, s: str) -> int:`` # # 在刚才的方法上进行优化就好了，可以减少空间复杂度`` # stack = [-1] indexing from the end `` # res = 0`` # for i in range(len(s)):`` # if s[i] == '(':`` # stack.append(i) `` # continue `` # stack.pop()`` # if not stack: stack.append(i) `` # else:`` # # print(i, stack)`` # res = max(res, i - stack[-1])`` # return res`

# ⁠剑指 Offer 55 - II. 平衡二叉树⁠⁠

`# class Solution:``# def isBalanced(self, root: TreeNode) -> bool:``# def helper(root):``# if root == None: return 0``# if helper(root.left) == -1: return -1``# if helper(root.right) == -1: return -1`` ``# return max(helper(root.left), helper(root.right)) + 1 if abs(helper(root.left) - helper(root.right)) <= 1 else -1`` `` # return helper(root) != -1`
`time limit exceeded!`

`class Solution:`` def isBalanced(self, root: TreeNode) -> bool:`` if not root: return True`` return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \`` self.isBalanced(root.left) and self.isBalanced(root.right)`
` def depth(self, root):`` if not root: return 0`` return max(self.depth(root.left), self.depth(root.right)) + 1`
Passed !

# ⁠剑指 Offer 66. 构建乘积数组⁠⁠

` class Solution:`` def constructArr(self, a: List[int]) -> List[int]:`` b, tmp = [1] * len(a), 1`` for i in range(1, len(a)):`` b[i] = b[i - 1] * a[i - 1] # 下三角`` for i in range(len(a) - 2, -1, -1): `` tmp *= a[i + 1] # 上三角`` b[i] *= tmp # 下三角 * 上三角`` return b`