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

 Here is the link. 

C# preorder traversal the original tree and find target

August 31, 2020
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

It is an easy problem to find target node using preorder traversal, and only extra task is to visit cloned tree as well in the same time.
Time complexity:
O(N), N is number of total nodes in the tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
     public TreeNode GetTargetCopy(TreeNode original, TreeNode cloned, TreeNode target)
        {
            if (original == null)
                return null;

            TreeNode found = null;

            preorderTraversal(original, cloned, target, ref found);
            return found; 
        }

        private void preorderTraversal(TreeNode original, TreeNode cloned, TreeNode target, ref TreeNode found)
        {
            if (found != null || original == null)
                return;

            if (original == target)
            {
                found = cloned;
                return;
            }

            preorderTraversal(original.left,  cloned.left,  target, ref found);
            preorderTraversal(original.right, cloned.right, target, ref found);
        }
}