LeetCode（Tree)1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

布满荆棘的人生 2023-09-26 20:37 45阅读 0赞

# 1.问题 #

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Example 1:  
![在这里插入图片描述][d01eb854ae2e4d29a823a159bf9fd623.png]

> Input: tree = \[7,4,3,null,null,6,19\], target = 3  
> Output: 3  
> Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:  
![在这里插入图片描述][e65fb873107f4c898fc6467b36f9c794.png]

> Input: tree = \[7\], target = 7  
> Output: 7

Example 3:  
![在这里插入图片描述][00fac6850aaf4299acd77eaf8d8865fc.png]

> Input: tree = \[8,null,6,null,5,null,4,null,3,null,2,null,1\], target = 4  
> Output: 4

Constraints:

*  The number of nodes in the tree is in the range \[1, 104\].
 *  The values of the nodes of the tree are unique.
 *  target node is a node from the original tree and is not null.

`Follow up: Could you solve the problem if repeated values on the tree are allowed?`

# 2. 解题思路 #

## 方法1： ##

> 解法一：递归  
> 递归是一种非常自然和直观的解法，可以通过对原二叉树和克隆树的遍历来查找目标节点。
> 
> 1.  首先判断当前节点是否为目标节点，如果是则返回当前节点。
> 2.  否则递归查找当前节点的左子树和右子树，并在克隆树中查找相应的节点。
> 3.  如果在左子树或右子树中找到了目标节点，则返回该节点，否则返回 null。
> 
> 时间复杂度：O(n)，其中 n 是树中节点的个数。在最坏情况下，需要遍历整棵树。  
> 空间复杂度：O(h)，其中 h 是树的高度。在最坏情况下，树的高度可以达到 n，因此空间复杂度为 O(n)。

## 方法2： ##

> 解法二：迭代  
> 迭代解法可以通过栈或队列来实现。在这里，我们可以使用栈来模拟递归的过程。具体实现：
> 
> 1.  首先将原二叉树的根节点和克隆树的根节点分别入栈。
> 2.  接下来，每次从栈中取出一个节点，判断该节点是否为目标节点，如果是则返回该节点。
> 3.  否则，将该节点的左子节点和克隆树中对应的节点入栈，并将该节点的右子节点和克隆树中对应的节点入栈。重复这个过程，直到栈为空。  
>     时间复杂度：O(n)，其中 n 是树中节点的个数。在最坏情况下，需要遍历整棵树。  
>     空间复杂度：O

## 方法3： ##

> 解法三：广度优先搜索的实现思路。
> 
> 1.  首先，我们用两个队列 queue1 和 queue2 来分别存储原始树和克隆树中的节点。然后，我们将原始树中的根节点和克隆树中的根节点分别加入队列 queue1 和 queue2 中。
> 2.  接着，我们开始进行广度优先搜索。在每一轮搜索中，我们先取出队列 queue1 中的队首节点 node1，再取出队列 queue2 中的队首节点 node2。
> 3.  如果 node1 等于目标节点 target，则返回 node2
> 4.  否则，我们分别将 node1 和 node2 的左右子节点加入队列 queue1 和 queue2 中。
> 5.  最终，如果队列 queue1 中的所有节点都被搜索完了，仍然没有找到目标节点 target，则说明目标节点不存在于原始树中，返回 null。  
>     在代码实现时，我们可以用 LinkedList 来实现队列，具体实现细节可以参考以下广度优先搜索的 Java 代码。

# 3. 代码 #

## 代码1： ##

> 解题思路基本相同，深度优先搜索通过递归

class Solution {
        
        public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        
           // 如果原始二叉树或克隆二叉树为空，直接返回null
            if (original == null || cloned == null) {
        
            return null;
            }
            // 如果当前节点是目标节点，直接返回
            if (original == target) {
        
                return cloned;
            }
    
            // 否则分别递归左右子树查找目标节点
            TreeNode leftResult = getTargetCopy(original.left, cloned.left, target);
            if (leftResult != null) {
        
                return leftResult;
            }
    
            TreeNode rightResult = getTargetCopy(original.right, cloned.right, target);
            if (rightResult != null) {
        
                return rightResult;
            }
    
            // 如果左右子树都没有找到目标节点，返回null
            return null;
        }
    
    }

## 代码2： ##

/**
     * 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) {
        
           // 首先将原始二叉树和克隆二叉树的根节点分别放入栈中
            Stack<TreeNode> originalStack = new Stack<>();
            Stack<TreeNode> clonedStack = new Stack<>();
            originalStack.push(original);
            clonedStack.push(cloned);
    
    
            while (!originalStack.isEmpty()) {
        
                // 分别弹出原始二叉树和克隆二叉树栈顶节点
                TreeNode currOriginal = originalStack.pop();
                TreeNode currCloned = clonedStack.pop();
    
                // 如果当前原始节点是目标节点，直接返回当前克隆节点
                if (currOriginal == target) {
        
                    return currCloned;
                }
    
                // 如果当前原始节点的左子树不为空，则将其入栈
                if (currOriginal.left != null) {
        
                    originalStack.push(currOriginal.left);
                    clonedStack.push(currCloned.left);
                }
    
                // 如果当前原始节点的右子树不为空，则将其入栈
                if (currOriginal.right != null) {
        
                    originalStack.push(currOriginal.right);
                    clonedStack.push(currCloned.right);
                }
            }
    
            // 如果遍历完原始二叉树都没有找到目标节点，返回null
            return null;     
        }
    
    }

## 代码3： ##

class Solution {
        
        public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        
            Queue<TreeNode> queue1 = new LinkedList<>();  // 原树的队列
            Queue<TreeNode> queue2 = new LinkedList<>();  // 克隆树的队列
            queue1.offer(original);  // 将原树的根节点入队
            queue2.offer(cloned);  // 将克隆树的根节点入队
    
            while (!queue1.isEmpty()) {
          // 迭代原树的队列
                int size = queue1.size();
    
                for (int i = 0; i < size; i++) {
          // 处理当前层级的所有节点
                    TreeNode node1 = queue1.poll();  // 弹出原树的节点
                    TreeNode node2 = queue2.poll();  // 弹出克隆树的节点
    
                    if (node1 == target) {
          // 如果原树的节点就是目标节点
                        return node2;  // 返回克隆树的节点
                    }
    
                    if (node1.left != null) {
          // 如果原树的左子节点不为空
                        queue1.offer(node1.left);  // 将其入队到原树的队列
                        queue2.offer(node2.left);  // 将其入队到克隆树的队列
                    }
    
                    if (node1.right != null) {
          // 如果原树的右子节点不为空
                        queue1.offer(node1.right);  // 将其入队到原树的队列
                        queue2.offer(node2.right);  // 将其入队到克隆树的队列
                    }
                }
            }
    
            return null;  // 没有找到目标节点，返回null
        }
    
    }

[d01eb854ae2e4d29a823a159bf9fd623.png]: https://img-blog.csdnimg.cn/d01eb854ae2e4d29a823a159bf9fd623.png
[e65fb873107f4c898fc6467b36f9c794.png]: https://img-blog.csdnimg.cn/e65fb873107f4c898fc6467b36f9c794.png
[00fac6850aaf4299acd77eaf8d8865fc.png]: https://img-blog.csdnimg.cn/00fac6850aaf4299acd77eaf8d8865fc.png