在受污染的二叉树中查找元素

难度:

标签:

题目描述

给出一个满足下述规则的二叉树：

root.val == 0
如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

示例 1：

输入：
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出：
[null,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True

示例 2：

输入：
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出：
[null,true,true,false]
解释：
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

示例 3：

输入：
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：
[null,true,false,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

提示：

TreeNode.val == -1
二叉树的高度不超过 20
节点的总数在 [1, 10^4] 之间
调用 find() 的总次数在 [1, 10^4] 之间
0 <= target <= 10^6

代码结果

运行时间: 57 ms, 内存: 19.8 MB

/*
  思路：
  1. 使用相同的还原逻辑，将二叉树的值存储在 HashSet 中。
  2. 在还原过程中，使用 Stream API 进行值的存储和查找。
*/

import java.util.HashSet;
import java.util.stream.Stream;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class FindElements {
    private HashSet<Integer> values;

    public FindElements(TreeNode root) {
        values = new HashSet<>();
        recoverTree(root, 0);
    }

    private void recoverTree(TreeNode node, int value) {
        if (node == null) return;
        node.val = value;
        values.add(value);
        Stream.of(new Object[][] {{node.left, 2 * value + 1}, {node.right, 2 * value + 2}})
            .forEach(pair -> recoverTree((TreeNode) pair[0], (Integer) pair[1]));
    }

    public boolean find(int target) {
        return values.contains(target);
    }
}

解释

方法:

题解的核心思路是通过遍历受污染的二叉树并逐步还原其原始值。由于每个节点的值都设为-1，需要根据二叉树的特性重新计算每个节点的值。根节点设置为0，对于任何节点，如果其值为x，则其左子节点的值为2x+1，右子节点的值为2x+2。通过深度优先搜索（DFS）遍历整个树，并在遍历过程中将每个节点的值存储在一个集合中，以便后续快速查找。初始化过程中，根据题目给定的污染树的结构，重新赋予每个节点正确的值并记录到集合中。在查找函数中，直接检查目标值是否存在于这个集合中。

时间复杂度:

O(n) for initialization, O(1) for each find operation

空间复杂度:

O(n)

代码细节讲解

🦆

在重设节点值的过程中，如何确保不会重复计算已经设置好值的节点？

▷

在重设节点值的过程中，DFS算法从根节点开始，递归地向下遍历每个子节点。每个节点在递归进入时就立即设置其值，并且这个值在递归过程中不会再改变。由于每个节点只被访问一次，因此每个节点的值只会被计算和设置一次，从而确保不会有重复计算。此外，递归函数不会再次访问已经设置好值的节点，因为每次递归调用都会传递到节点的子节点，而不是已处理的父节点或兄弟节点。

🦆

为什么选择使用HashSet存储节点值，而不是其他数据结构如列表或字典？

▷

HashSet被选用来存储节点值主要是因为其高效的查找性能。HashSet的平均时间复杂度为O(1)对于插入和查找操作，这是因为HashSet基于哈希表实现。相比之下，如果使用列表存储节点值，查找操作的时间复杂度将为O(n)，这在节点数量较多时会显著降低性能。使用字典虽然也可以达到O(1)的查找和插入性能，但相较于HashSet，字典会存储额外的键值对信息，这在本题中没有必要，因此HashSet是一个更为节省空间且效率高的选择。

🦆

在DFS过程中，如果二叉树非常深会不会导致栈溢出？如何优化以防止这种情况？

▷

如果二叉树非常深，使用递归的DFS确实可能导致栈溢出，因为每一层递归调用都会消耗一定的栈空间。为了优化并防止栈溢出，可以采用迭代的方式使用DFS而不是递归。这通常涉及到使用一个显式的栈来模拟递归过程。在迭代DFS中，你可以手动控制栈的推送和弹出，这有助于避免深度递归造成的栈溢出问题。此外，还可以考虑使用广度优先搜索(BFS)，它使用队列而不是栈，从而避免深度递归所带来的风险。

🦆

find函数的性能是否完全依赖于HashSet的性能？在什么情况下这可能成为性能瓶颈？

▷

find函数的性能确实很大程度上依赖于HashSet的性能，尤其是其查找操作的效率。HashSet的查找操作平均时间复杂度是O(1)，但在最坏情况下，如果发生大量哈希冲突，性能可能退化到O(n)。这种情况虽然不常见，但在极端情况下（如哈希函数选取不当，或者存储大量接近哈希极限的数据时）可能发生。如果HashSet的性能成为瓶颈，可以考虑重新评估哈希函数的选择，或者使用更复杂的数据结构，如平衡二叉搜索树，这些结构虽然查找时间复杂度为O(log n)，但提供更稳定的性能。

在受污染的二叉树中查找元素

题目描述

代码结果

解释

代码细节讲解

相关问题