Post Order Processing
or Bottom up recursion
Traverse
563. Binary Tree Tilt
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
def findTilt(self, root: Optional[TreeNode]) -> int:
def dfs(node):
nonlocal tilt
if not node:
return 0
left_total = dfs(node.left)
right_total = dfs(node.right)
tilt += abs(left_total - right_total)
return node.val + left_total + right_total
tilt = 0
dfs(root)
return tilt
Analysis
- Python
def findTilt(self, root: Optional[TreeNode]) -> int:
stack = [(root, False)]
result = {}
tilt = 0
while stack:
node, visited = stack.pop()
if not node:
result[node] = 0
else:
if visited:
left_total = result[node.left]
right_total = result[node.right]
tilt += abs(left_total - right_total)
result[node] = node.val + left_total + right_total
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return tilt
110. Balanced Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(node):
if not node:
return True, 0
left_result, left_height = dfs(node.left)
right_result, right_height = dfs(node.right)
node_height = 1 + max(left_height, right_height)
if abs(left_height - right_height) > 1:
return False, node_height
return left_result and right_result, node_height
return dfs(root)[0]
Analysis
- Python
def isBalanced(self, root: Optional[TreeNode]) -> bool:
stack = [(root, False)]
result = {}
while stack:
node, visited = stack.pop()
if not node:
result[node] = True, 0
else:
if visited:
left_result, left_height = result[node.left]
right_result, right_height = result[node.right]
node_height = 1 + max(left_height, right_height)
if abs(left_height - right_height) > 1:
result[node] = False, node_height
else:
result[node] = left_result and right_result, node_height
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return result.get(root, (True, 0))[0]
Children Sum in a Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
def isSumProperty(self, root):
def dfs(node):
if not node:
return 0, True
if not node.left and not node.right:
return node.data, True
left_total, left_result = dfs(node.left)
right_total, right_result = dfs(node.right)
child_total = left_total + right_total
return node.data, left_result and right_result and node.data == child_total
return dfs(root)[1]
Analysis
- Python
def isSumProperty(self, root):
stack = [(root, False)]
result = {}
while stack:
node, visited = stack.pop()
if not node:
result[node] = 0, True
elif not node.left and not node.right:
result[node] = node.data, True
else:
if visited:
left_total, left_result = result[node.left]
right_total, right_result = result[node.right]
child_total = left_total + right_total
result[node] = (
node.data,
left_result and right_result and node.data == child_total,
)
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return result.get(root, (True, 0))[1]
1973. Count Nodes Equal to Sum of Descendants
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
def equalToDescendants(self, root: Optional[TreeNode]) -> int:
def dfs(node):
nonlocal count
if not node:
return 0
left_total = dfs(node.left)
right_total = dfs(node.right)
descendant_total = left_total + right_total
count += descendant_total == node.val
return node.val + descendant_total
count = 0
dfs(root)
return count
Analysis
- Python
def equalToDescendants(self, root: Optional[TreeNode]) -> int:
stack = [(root, False)]
result = {}
count = 0
while stack:
node, visited = stack.pop()
if not node:
result[node] = 0
else:
if visited:
left_total = result[node.left]
right_total = result[node.right]
descendant_total = left_total + right_total
count += descendant_total == node.val
result[node] = node.val + descendant_total
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return count
508. Most Frequent Subtree Sum
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
import collections
def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
nonlocal max_freq
if not node:
return 0
left_total = dfs(node.left)
right_total = dfs(node.right)
total = node.val + left_total + right_total
frequency[total] += 1
max_freq = max(max_freq, frequency[total])
return total
frequency = collections.defaultdict(int)
max_freq = 0
dfs(root)
return [total for total, freq in frequency.items() if freq == max_freq]
Analysis
- Python
import collections
def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
stack = [(root, False)]
result = {}
frequency = collections.defaultdict(int)
max_freq = 0
while stack:
node, visited = stack.pop()
if not node:
result[node] = 0
else:
if visited:
left_total = result[node.left]
right_total = result[node.right]
total = node.val + left_total + right_total
frequency[total] += 1
max_freq = max(max_freq, frequency[total])
result[node] = total
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return [total for total, freq in frequency.items() if freq == max_freq]
Manipulate Tree
Transform to Sum Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
def toSumTree(self, root):
def dfs(node):
if not node:
return 0
left_total = dfs(node.left)
right_total = dfs(node.right)
total = left_total + right_total + node.data
node.data = left_total + right_total
return total
dfs(root)
Analysis
- Python
def toSumTree(self, root):
stack = [(root, False)]
result = collections.defaultdict(int)
while stack:
node, visited = stack.pop()
if node:
if visited:
left_total = result[node.left]
right_total = result[node.right]
total = left_total + right_total + node.data
node.data = left_total + right_total
result[node] = total
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))