LEETCODE 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree 解题思路分析

题目大意:

给你两颗二叉树 original 和cloned,以及一个 original  树种的节点对象 target 。

cloned树是 original树的拷贝。

请返回 cloned 树种相对应的 target 节点对象。

注意,你不能改变2棵树的内容以及 target节点,另外返回结果必须是cloned树中的对象。

进阶:如果每棵树中存在数值相同的节点,你该如何处理

示例1:

输入: tree = [7,4,3,null,null,6,19], target = 3
输出: 3
解释: 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.

示例2:

输入: tree = [7], target =  7
输出: 7

示例3:

输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
输出: 4

示例4:

输入: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
输出: 5

示例5:

输入: tree = [1,2,null,3], target = 2
输出: 2

提示:

  • 二叉树中节点值的范围在 [1, 10^4] 之间
  • 每颗树中所有节点的值是唯一的
  • target 节点是 original 树中的节点,并且它是非空的

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1379

解题思路分析:

对于二叉树题目,bfs或者dfs是非常好的解题方案,本题也不例外,我们可以使用dfs深度优先搜索来解题。dfs时,我们将original 和cloned两棵树的当前节点同时传入dfs方法中,如果当前original节点与target相同,那么,当前 cloned 节点即是返回结果。反之继续向左右子节点进行dfs。

实现代码:

public final TreeNode getTargetCopy(final TreeNode original, 
                        final TreeNode cloned, final TreeNode target) {
    // 如果original当前节点等于target节点,返回对应的cloned节点
    if(original.equals(target)) return cloned;
    // 如果左子节点不为空
    if(original.left!=null){
        // dfs至左子节点
        TreeNode left=getTargetCopy(original.left,cloned.left,target);
        // 如果dfs结果不为空,返回该结果
        if(left!=null) return left; 
    }
    // 如果右子节点不为空
    if(original.right!=null){
        // dfs至右子节点,并返回该结果
        return getTargetCopy(original.right,cloned.right,target);
    }
    return null; 
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.

Memory Usage: 44.8 MB, less than 100.00% of Java online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1379-find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。