103. Binary Tree Zigzag Level Order Traversal (medium)
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
que, temp, ans = [root], [], [[]]
level = 0
while que:
target = que.pop(0)
ans[level].append(target.val)
if target.left:
temp.append(target.left)
if target.right:
temp.append(target.right)
if len(que) == 0 and len(temp) > 0:
if level % 2 == 1:
ans[level] = ans[level][::-1]
que = temp[:]
temp = []
ans.append([])
level += 1
if level % 2 == 1:
ans[level] = ans[level][::-1]
return ans
700. Search in a Binary Search Tree (easy)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return None
elif root.val == val:
return root
elif root.val < val:
return self.searchBST(root.right, val)
elif root.val > val:
return self.searchBST(root.left, val)
701. Insert into a Binary Search Tree (medium)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
def dfs(node):
nonlocal val
if not node:
return TreeNode(val)
if val < node.val:
temp = dfs(node.left)
if temp: node.left = temp
if val > node.val:
temp = dfs(node.right)
if temp: node.right = temp
return None
dfs(root)
return root
98. Validate Binary Search Tree (medium)
class Solution(object):
def isValidBST(self, root, lessThan = float('inf'), largerThan = float('-inf')):
if not root:
return True
if root.val <= largerThan or root.val >= lessThan:
return False
return self.isValidBST(root.left, min(lessThan, root.val), largerThan) and self.isValidBST(root.right, lessThan, max(root.val, largerThan))