LeetCode 1485. 克隆含随机指针的二叉树

Categories:

题目描述
思路分析
1. 解法一：同步 DFS（推荐）
相似题目

题目描述

✅ 1485. 克隆含随机指针的二叉树

思路分析

解法一：同步 DFS（推荐）

核心思路：

同时遍历原树与克隆树。

当原树节点等于 target 时，返回克隆树对应节点。

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(h)。

class Solution {
    public TreeNode getTargetCopy(TreeNode original, TreeNode cloned, 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);
    }
}

func getTargetCopy(original *TreeNode, cloned *TreeNode, target *TreeNode) *TreeNode {
    if original == nil {
        return nil
    }
    if original == target {
        return cloned
    }
    left := getTargetCopy(original.Left, cloned.Left, target)
    if left != nil {
        return left
    }
    return getTargetCopy(original.Right, cloned.Right, target)
}

相似题目

题目	难度	考察点
572. 另一棵树的子树	简单	树遍历
100. 相同的树	简单	树遍历
101. 对称二叉树	简单	树遍历
112. 路径总和	简单	DFS
617. 合并二叉树	简单	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/16372136