2024.3.12力扣每日一题——在受污染的二叉树中查找元素

题目来源

力扣每日一题；题序：1261

我的题解

方法一 深度优先遍历+哈希表

使用深度优先遍历重构原始二叉树，然后在重构过程中使用Set记录有哪些元素。

时间复杂度：O(n)
空间复杂度：O(n)

class FindElements {
    Set<Integer> set;
    public FindElements(TreeNode root) {
        set=new HashSet<>();
        dfs(root,0);
    }
    
    public boolean find(int target) {
        return set.contains(target);
    }
    public void dfs(TreeNode root,int x){
        if(root==null)
            return ;
        root.val=x;
        set.add(x);
        dfs(root.left,2*x+1);
        dfs(root.right,2*x+2);
    }
}

方法二 深度优先遍历+位运算

细节参考官方题解。

时间复杂度：O(n)
空间复杂度：O(n)

class FindElements {
    private TreeNode root;

    public FindElements(TreeNode root) {
        dfs(root, 0);
        this.root = root;
    }
    
    public boolean find(int target) {
        target++;
        int k = 30 - Integer.numberOfLeadingZeros(target);
        TreeNode node = root;
        while (k >= 0 && node != null) {
            if ((target & (1 << k)) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            k--;
        }
        return node != null;
    }

    private void dfs(TreeNode node, int val) {
        if (node == null) {
            return;
        }
        node.val = val;
        dfs(node.left, val * 2 + 1);
        dfs(node.right, val * 2 + 2);
    }
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~