Friday, July 17th, 2020 🤔

⁠
`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.

2. In-order traversal

Approach:

Use a stack to store the nodes

⁠

⁠
`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:

Example 2:

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:

2. Stack

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

Passed !

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

⁠

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.

Friday, July 17th, 2020 🤔

⁠98. Validate Binary Search Tree⁠⁠