Two Trees
100. Same Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
Interactive Visualization
Analysis
- Python
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
def dfs(a, b):
if not a and not b:
return True
if not a or not b:
return False
if a.val != b.val:
return False
return dfs(a.left, b.left) and dfs(a.right, b.right)
return dfs(p, q)
Interactive Visualization
Analysis
- Python
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack = [(p, q)]
while stack:
a, b = stack.pop()
if not a and not b:
continue
if not a or not b:
return False
if a.val != b.val:
return False
stack.append((a.left, b.left))
stack.append((a.right, b.right))
return True
101. Symmetric Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(left, right):
if not right and not left:
return True
if not right or not left:
return False
if left.val != right.val:
return False
return dfs(left.left, right.right) and dfs(left.right, right.left)
return dfs(root, root)
Analysis
- Python
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
stack = [(root, root)]
while stack:
left, right = stack.pop()
if not right and not left:
continue
if not right or not left:
return False
if left.val != right.val:
return False
stack.append((left.left, right.right))
stack.append((left.right, right.left))
return True
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def getTargetCopy(
self, original: TreeNode, cloned: TreeNode, target: TreeNode
) -> TreeNode:
def dfs(a, b):
if a and b:
if a == target:
return b
left_result = dfs(a.left, b.left)
right_result = dfs(a.right, b.right)
return left_result or right_result
return dfs(original, cloned)
Analysis
- Python
def getTargetCopy(
self, original: TreeNode, cloned: TreeNode, target: TreeNode
) -> TreeNode:
stack = [(original, cloned)]
while stack:
a, b = stack.pop()
if a and b:
if a == target:
return b
stack.append((a.right, b.right))
stack.append((a.left, b.left))
return None
Analysis
- Python
import collections
def getTargetCopy(
self, original: TreeNode, cloned: TreeNode, target: TreeNode
) -> TreeNode:
queue = collections.deque([(original, cloned)])
while queue:
for _ in range(len(queue)):
a, b = queue.popleft()
if a and b:
if a == target:
return b
queue.append((a.left, b.left))
queue.append((a.right, b.right))
return None