Leetcode # 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Problem

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree

Solution: DFS

n := number of nodes in the original tree

Time Complexity: O(n)
Space Complexity: O(log(n))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
    stack = [cloned]
    while stack:
      curr = stack.pop()
      if curr.val == target.val:
        return curr
      for child in [curr.left, curr.right]:
        if child: 
          stack.append(child)  

Last Updated on 2023/09/11 by A1go