Summary of Binary Tree. (preorder, inorder, postorder, level-order traversal not included)
LeetCode 101 Symmetric Tree
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return False
que = deque()
que.append(root.left)
que.append(root.right)
while que:
left = que.popleft()
right = que.popleft()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
que.append(left.left)
que.append(right.right)
que.append(left.right)
que.append(right.left)
return True
Similar: LeetCode 100 Same Tree, LeetCode 572 Subtree of Another Tree.
LeetCode 104 Maximum Depth of Binary Tree
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
max_depth = 0
if not root:
return max_depth
que = deque([root])
while que:
max_depth += 1
size = len(que)
for i in range(size):
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return max_depth
Similar: LeetCode 559 Maximum Depth of N-ary Trees
LeetCode 111 Minimum Depth of Binary Tree
# 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 minDepth(self, root: Optional[TreeNode]) -> int:
que = deque([root])
min_depth = 0
if not root:
return min_depth
while que:
size = len(que)
min_depth += 1
for i in range(size):
cur = que.popleft()
if not cur.left and not cur.right:
return min_depth
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return min_depth
LeetCode 222 Count Complete Tree Nodes
# 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 countNodes(self, root: Optional[TreeNode]) -> int:
que = deque([root])
cnt = 0
if not root:
return cnt
while que:
size = len(que)
for i in range(size):
cur = que.popleft()
cnt += 1
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return cnt
LeetCode 110 Balanced Binary Tree
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def get_height(node):
if not node:
return 0
leftHeight = get_height(node.left)
rightHeight = get_height(node.right)
if leftHeight == -1: # left
return -1
if rightHeight == -1: # right
return -1
if abs(leftHeight - rightHeight) > 1: # root
return -1
else:
return 1 + max(leftHeight, rightHeight)
return get_height(root) != -1
LeetCode 257 Binary Tree Paths
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
stack = [root]
cur_path = [str(root.val)]
result = []
while stack:
cur = stack.pop()
path = cur_path.pop()
if not cur.left and not cur.right:
result.append(path)
if cur.right:
stack.append(cur.right)
cur_path.append(path+'->'+ str(cur.right.val))
if cur.left:
stack.append(cur.left)
cur_path.append(path+'->'+ str(cur.left.val))
return result
LeetCode 404 Sum of Left Leaves
# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
que = deque()
if not root:
return que
que.append(root)
res = 0
while que:
cur = que.popleft()
if cur.left != None and cur.left.left == None and cur.left.right == None:
res += cur.left.val
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return res
LeetCode 513 Find Bottom Left Tree Value
# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
que = deque([root])
if not root:
return None
res = 0
while que:
size = len(que)
for i in range(size):
if i == 0:
res = que[i].val
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return res
LeetCode 112 Path Sum
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
stack = []
if not root: return False
stack.append((root, root.val))
while stack:
cur_node, cur_val = stack.pop()
if not cur_node.left and not cur_node.right and cur_val == targetSum:
return True
if cur_node.right:
stack.append((cur_node.right, cur_node.right.val + cur_val))
if cur_node.left:
stack.append((cur_node.left, cur_node.left.val + cur_val))
return False
LeetCode 226 Invert Binary Tree
Pre-order traversal.
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
que = deque([root])
while que:
node = que.popleft()
node.left, node.right = node.right, node.left
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
return root
Breadth first search. Level-order traversal.
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
que = deque([root])
while que:
size = len(que)
for i in range(size):
node = que.popleft()
node.left, node.right = node.right, node.left
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
return root
LeetCode 654 Maximum Binary Tree
# 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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
cur_val = max(nums)
root = TreeNode(cur_val)
separator = nums.index(cur_val)
left = nums[:separator]
right = nums[separator+1:]
root.left = self.constructMaximumBinaryTree(left)
root.right = self.constructMaximumBinaryTree(right)
return root
LeetCode 617 Merge Two Binary Trees
# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val # middle
root1.left = self.mergeTrees(root1.left, root2.left) # left
root1.right = self.mergeTrees(root1.right, root2.right) # right
return root1
# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
que = deque()
que.append(root1)
que.append(root2)
while que:
node1=que.popleft()
node2=que.popleft()
if node1.left and node2.left:
que.append(node1.left)
que.append(node2.left)
if node1.right and node2.right:
que.append(node1.right)
que.append(node2.right)
node1.val += node2.val
if not node1.left and node2.left:
node1.left = node2.left
if not node1.right and node2.right:
node1.right = node2.right
return root1
LeetCode 236 Lowest Common Ancestor of a Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if left:
return left
return right
