1379. 找出克隆二叉树中的相同节点

迈不过友情╰ 2022-12-20 09:06 165阅读 0赞

# 题目来源 #

[1379. 找出克隆二叉树中的相同节点][1379.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

original树和cloned树的结构，以及所有节点对应的值都是一模一样。基本可以理解成两个"相同"的树（但是内存地址不同，本质上并不一样）。

要在original树中来寻找target，自然想到的就是遍历original树。那么正常的前中后序遍历，应该选择哪一个呢？

前序遍历。

因为只要original和target相同，则表示对应的cloned就是我们想要的节点。这个遍历过程，和左右子树并没有关系。所以我们选择前序遍历。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    class Solution {
        
        public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        
            if (original == null  || cloned == null){
        
                return null;
            }
    
            if (original == target){
        
                return cloned;
            }
    
            TreeNode res = getTargetCopy(original.left, cloned.left, target);
            if (res != null){
        
                return res;
            }
    
            res =  getTargetCopy(original.right, cloned.right, target);
            if (res != null){
        
                return res;
            }
    
            return null;
        }
    }

[1379.]: https://leetcode-cn.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9577ed83133d45fab73a79f22140e56b.png