Binary Tree Top-Down DFS¶
Table of Contents¶
- 104. Maximum Depth of Binary Tree (Easy)
- 111. Minimum Depth of Binary Tree (Easy)
- 112. Path Sum (Easy)
- 129. Sum Root to Leaf Numbers (Medium)
- 199. Binary Tree Right Side View (Medium)
- 1448. Count Good Nodes in Binary Tree (Medium)
- 1457. Pseudo-Palindromic Paths in a Binary Tree (Medium)
- 1315. Sum of Nodes with Even-Valued Grandparent (Medium)
- 988. Smallest String Starting From Leaf (Medium)
- 1026. Maximum Difference Between Node and Ancestor (Medium)
- 1022. Sum of Root To Leaf Binary Numbers (Easy)
- 623. Add One Row to Tree (Medium)
- 1372. Longest ZigZag Path in a Binary Tree (Medium)
- 971. Flip Binary Tree To Match Preorder Traversal (Medium)
- 2689. Extract Kth Character From The Rope Tree (Easy) 👑
- 298. Binary Tree Longest Consecutive Sequence (Medium) 👑
- 1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree (Medium) 👑
- 545. Boundary of Binary Tree (Medium) 👑
104. Maximum Depth of Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def maxDepthRecursive(root: Optional[TreeNode]) -> int:
if not root:
return 0
left = maxDepthRecursive(root.left)
right = maxDepthRecursive(root.right)
return 1 + max(left, right)
# DFS
def maxDepthDFS(root: Optional[TreeNode]) -> int:
res = 0
def dfs(node, cnt):
if node is None:
return
cnt += 1
nonlocal res
res = max(res, cnt)
dfs(node.left, cnt)
dfs(node.right, cnt)
dfs(root, 0)
return res
# Iterative
def maxDepthIterative(root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
res = 0
while q:
res += 1
n = len(q)
for _ in range(n):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \
# 3 4
# /
# 5
assert maxDepthRecursive(root) == 4
assert maxDepthDFS(root) == 4
assert maxDepthIterative(root) == 4
111. Minimum Depth of Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Iterative
def minDepthIterative(root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
res = 0
while q:
res += 1
for _ in range(len(q)):
node = q.popleft()
if not node.left and not node.right:
return res
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
# Recursive
def minDepthRecursive(root: Optional[TreeNode]) -> int:
if root is None:
return 0
if root.left is None and root.right is not None:
return 1 + minDepthRecursive(root.right)
if root.left is not None and root.right is None:
return 1 + minDepthRecursive(root.left)
return 1 + min(minDepthRecursive(root.left), minDepthRecursive(root.right))
root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
"""
____1
/ \
2__ 2
/ \
3 4
/
5
"""
print(minDepthIterative(root)) # 2
print(minDepthRecursive(root)) # 2
112. Path Sum¶
from typing import Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Recursive
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
targetSum -= root.val
return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)
root = build([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, None, None, 1])
print(root)
# 5___
# / \
# ___4 _8
# / / \
# 11 13 4
# / \ \
# 7 2 1
print(hasPathSum(root, 22)) # True
129. Sum Root to Leaf Numbers¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
class sumNumbers:
def dfs(self, root: Optional[TreeNode]) -> int:
self.res = 0
def dfs(node, cur):
if not node:
return
cur = cur * 10 + node.val
if not node.left and not node.right:
self.res += cur
return
dfs(node.left, cur)
dfs(node.right, cur)
dfs(root, 0)
return self.res
if __name__ == "__main__":
root = [1, 2, 3]
root = build(root)
print(root)
# 1
# / \
# 2 3
assert sumNumbers().dfs(root) == 25
199. Binary Tree Right Side View¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree BFS
def rightSideViewBFS(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
q = deque([root])
res = []
while q:
n = len(q)
for i in range(n):
node = q.popleft()
if i == n - 1:
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
# Binary Tree DFS
def rightSideViewDFS(root: Optional[TreeNode]) -> List[int]:
"""后序遍历，先右后左，遇到的第一个节点就是该深度的最右侧节点"""
ans = []
def dfs(node, depth):
if node is None:
return
if depth == len(ans): # 这个深度首次遇到
ans.append(node.val)
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return ans
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, None, 3, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \ \
# 3 4 3
# /
# 5
assert rightSideViewBFS(root) == [1, 2, 3, 5]
assert rightSideViewDFS(root) == [1, 2, 3, 5]
1448. Count Good Nodes in Binary Tree¶
from typing import List
from binarytree import Node as TreeNode
from binarytree import build
# Tree
def goodNodes(root: TreeNode) -> int:
def dfs(node, max_val):
if not node:
return 0
good = 1 if node.val >= max_val else 0
max_val = max(max_val, node.val)
good += dfs(node.left, max_val)
good += dfs(node.right, max_val)
return good
return dfs(root, root.val)
root = build([3, 1, 4, 3, None, 1, 5])
print(root)
# 3__
# / \
# 1 4
# / / \
# 3 1 5
print(goodNodes(root)) # 4
1457. Pseudo-Palindromic Paths in a Binary Tree¶
1315. Sum of Nodes with Even-Valued Grandparent¶
988. Smallest String Starting From Leaf¶
1026. Maximum Difference Between Node and Ancestor¶
1022. Sum of Root To Leaf Binary Numbers¶
623. Add One Row to Tree¶
from collections import deque
from copy import deepcopy
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BFS
def addOneRow_bfs(root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
if not root:
return None
if depth == 1:
new = TreeNode(val)
new.left = root
return new
q = deque([root])
cur = 1
while q:
size = len(q)
for _ in range(size):
node = q.popleft()
if cur == depth - 1:
old_left, old_right = node.left, node.right
node.left, node.right = TreeNode(val), TreeNode(val)
node.left.left = old_left
node.right.right = old_right
else:
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
cur += 1
return root
# DFS
def addOneRow_dfs(root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
if depth == 1:
new = TreeNode(val)
new.left = root
return new
def dfs(node, cur):
if not node:
return
if cur == depth - 1:
old_left, old_right = node.left, node.right
node.left = TreeNode(val, old_left, None)
node.right = TreeNode(val, None, old_right)
else:
dfs(node.left, cur + 1)
dfs(node.right, cur + 1)
dfs(root, 1)
return root
if __name__ == "__main__":
root = build([4, 2, 6, 3, 1, 5])
print(root)
# __4__
# / \
# 2 6
# / \ /
# 3 1 5
print(addOneRow_bfs(deepcopy(root), 1, 2))
# 4
# / \
# __1 1__
# / \
# 2 6
# / \ /
# 3 1 5
print(addOneRow_dfs(deepcopy(root), 1, 2))
# 4
# / \
# __1 1__
# / \
# 2 6
# / \ /
# 3 1 5
1372. Longest ZigZag Path in a Binary Tree¶
971. Flip Binary Tree To Match Preorder Traversal¶
2689. Extract Kth Character From The Rope Tree 👑¶
298. Binary Tree Longest Consecutive Sequence 👑¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree
def longestConsecutive(root: Optional[TreeNode]) -> int:
res = 0
def dfs(node):
if not node:
return 0
left, right = dfs(node.left), dfs(node.right)
cur = 1
if node.left and node.left.val == (node.val + 1):
cur = max(cur, left + 1)
if node.right and node.right.val == (node.val + 1):
cur = max(cur, right + 1)
nonlocal res
res = max(res, cur)
return cur
dfs(root)
return res
if __name__ == "__main__":
root = build([1, 3, 2, 4, None, None, None, 5])
print(root)
# 1
# / \
# 3 2
# /
# 4
# /
# 5
print(longestConsecutive(root)) # 3