java递归遍历树重复对象问题

在Java中，递归遍历树形结构（如二叉树、层次遍历等）可能会遇到重复对象的问题，主要是因为递归过程中没有有效的去重机制。当你深度优先地访问节点时，如果两个节点的数据相等，而它们又不在同一个分支上，就可能导致多次添加到结果集合中。

例如，在一个简单的二叉搜索树中，递归查找并添加所有叶子节点值到一个列表中时，如果没有对已经访问过的节点进行标记，那么当遇到相同的值时，就会被错误地添加多次。

解决这个问题的一个常见方法是在递归函数中引入额外的状态（如哈希集合或标记数组），来跟踪哪些值已经被处理过。每次访问新节点时，先检查其值是否已经在集合或数组中，如果不是则继续遍历，如果是则跳过这个节点。

以下是使用Java解决递归遍历树重复对象问题的一个示例：

import java.util.HashSet;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    // 省略构造函数和equals方法
}

public List<Integer> getUniqueValues(TreeNode root) {
    HashSet<Integer> uniqueSet = new HashSet<>();
    List<Integer> result = new ArrayList<>();
    dfs(root, uniqueSet, result);
    return result;
}

private void dfs(TreeNode node, HashSet<Integer> uniqueSet, List<Integer> result) {
    if (node == null) {
        return;
    }
    
    if (!uniqueSet.contains(node.val)) { // 检查值是否已存在
        uniqueSet.add(node.val); // 添加到集合中防止重复
        result.add(node.val); // 添加到结果列表
    }

    // 递归处理左右子节点
    dfs(node.left, uniqueSet, result);
    dfs(node.right, uniqueSet, result);
}