33/leetcode
/101. 对称二叉树.py
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return max(left_depth, right_depth) + 1
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
def is_mirror(left, right):
if left is None and right is None:
return True
if left is None or right is None:
return False
if left.val != right.val:
return False
return is_mirror(left.left, right.right) and is_mirror(left.right, right.left)
return is_mirror(root.left, root.right)
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if root is None:
return False
def is_identical(root, subRoot):
if root is None and subRoot is None:
return True
if root is None or subRoot is None:
return False
if root.val != subRoot.val:
return False
return is_identical(root.left, subRoot.left) and is_identical(root.right, subRoot.right)
return is_identical(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
/116. 填充每个节点的下一个右侧节点指针.py
from typing import List
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if root is None:
return res
stack = [(root, 0)]
while stack:
node, level = stack.pop()
if level >= len(res):
res.append([])
res[level].append(node.val)
if node.left is not None:
stack.append((node.left, level + 1))
if node.right is not None:
stack.append((node.right, level + 1))
for i in range(len(res)):
if i % 2 == 1:
res[i] = res[i][::-1]
return res
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if root is None:
return res
stack = [(root, 0)]
while stack:
node, level = stack.pop()
if level >= len(res):
res.append([])
res[level].append(node.val)
if node.left is not None:
stack.append((node.left, level + 1))
if node.right is not None:
stack.append((node.right, level + 1))
return res
/114. 二叉树展开为链表.py
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
if root.left is None and root.right is None:
return targetSum == root.val
targetSum -= root.val
return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
stack = [(root, targetSum - root.val)]
while stack:
node, target_sum = stack.pop()
if node.left is None and node.right is None:
if target_sum == 0:
return True
else:
continue
if node.left is not None:
stack.append((node.left, target_sum))
if node.right is not None:
stack.append((node.right, target_sum))
return False
/115. 不同的二叉搜索树.py
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
if root is None:
return root
if root.left is not None:
self.flatten(root.left)
root.right = root.left
tmp = root.left
root.left = None
while tmp.right is not None:
tmp = tmp.right
tmp.right = self.flatten(root.right)
else:
self.flatten(root.right)
return root
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
if root is None:
return root
stack = [root]
while stack:
node = stack.pop()
if node is None:
continue
if node.left is not None:
stack.append(node.right)
stack.append(node.left)
node.right = node.left
node.left = None
if node.right is not None:
stack.append(node.right)
return root