98. Validate Binary Search Tree · Leetcode Daily Practice

Leetcode Daily Practice

98. Validate Binary Search Tree

剑指 Offer 13. 机器人的运动范围

Untitled

Explore

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.

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

⁠

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.