JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-07-11
目录

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

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给你两棵二叉树,原始树 original 和克隆树 cloned,以及一个位于原始树 original 中的目标节点 target。

其中,克隆树 cloned 是原始树 original 的一个 副本 。

请找出在树 cloned 中,与 target 相同 的节点,并返回对该节点的引用(在 C/C++ 等有指针的语言中返回 节点指针,其他语言返回节点本身)。

注意:你 不能 对两棵二叉树,以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。

示例 1:

输入: tree = [7,4,3,null,null,6,19], target = 3
输出: 3
解释: 上图画出了树 original 和 cloned。target 节点在树 original 中,用绿色标记。答案是树 cloned 中的黄颜色的节点(其他示例类似)。

示例 2:

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

示例 3:

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

提示:

  • 树中节点的数量范围为 [1, 104] 。
  • 同一棵树中,没有值相同的节点。
  • target 节点是树 original 中的一个节点,并且不会是 null 。

进阶:如果树中允许出现值相同的节点,将如何解答?

# 思路

递归

# 解法


/**
 * 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) return null;
        if (original == target) return cloned;
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if (left!=null) return left;
        return getTargetCopy(original.right, cloned.right, target);      
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1633. 各赛事的用户注册率 Java
07-02
02
1636. 按照频率将数组升序排序 Java
07-02
03
1639. 通过给定词典构造目标字符串的方案数 Java
07-02
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式