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

题目来源

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

题目描述

题目解析

题目解析1

先不要看cloned，我们就来看看original。如果想要去original中寻找和target中一样的（找位置），那应该怎么找呢？

// 返回要找的
TreeNode* getTargetCopy(TreeNode* original,  TreeNode* target) {
    // 没有找到
    if(original == NULL){
        return NULL;
    }

    // 当前树就是要找的
    if(original == target){
        return original;
    }

    // 没有找到，那么去左子树中找
    TreeNode *ans = getTargetCopy(original->left, target);
    if(ans != NULL){  // 左子树中找到了
        return ans;     //就不用去右子树中找了，直接返回
    }
    
    ans = getTargetCopy(original->right, target);
    if(ans != NULL){ //右子树中找到了
        return ans;  // 那就直接返回
    }

     // 左右子树中均找不到
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

又因为cloned是target的克隆，因此

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
    if(original == NULL){
        return NULL;
    }
    
    if(original == target){
        return cloned;
    }
    
    TreeNode *ans = getTargetCopy(original->left, cloned->left, target);
    if(ans != NULL){
        return ans;
    }
    
    ans = getTargetCopy(original->right, cloned->right, target);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目解析2

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33