LeetCode 1261. 在受污染的二叉树中查找元素 ，对比树的DFS常规解法、logn优化解法。

题目

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

https://leetcode.cn/problems/find-elements-in-a-contaminated-binary-tree/

Given a binary tree with the following rules:

  1. root.val == 0
  2. If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
  3. If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2 Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

Implement the FindElements class:

  • FindElements(TreeNode* root) Initializes the object with a contaminated binary tree and recovers it.
  • bool find(int target) Returns true if the target value exists in the recovered binary tree.

题目给定了一个被污染的二叉树（结构不变，值需要恢复）。实现一个数据结构，支持查询。

DFS

思路

我首先想到用DFS的思路来搜索，遍历整棵树。

关键点：

  • 维护一个干净的TreeNode，构造器中恢复对应值；
  • 使用DFS展开搜索；

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

static class FindElements {

    TreeNode newRoot;

    public FindElements(TreeNode root) {
        newRoot = new TreeNode(0);
        newRoot.left = rebuild(newRoot, root.left, true);
        newRoot.right = rebuild(newRoot, root.right, false);
    }

    private TreeNode rebuild(TreeNode parent, TreeNode node, boolean left) {
        if (node == null) {
            return null;
        }
        TreeNode curr = new TreeNode();
        curr.val = left ? 2 * parent.val + 1 : 2 * parent.val + 2;
        curr.left = rebuild(curr, node.left, true);
        curr.right = rebuild(curr, node.right, false);
        return curr;
    }

    public boolean find(int target) {
        if (target < 0) return false;
        return find(newRoot, target);
    }

    private boolean find(TreeNode node, int target) {
        if (node == null) {
            return false;
        }
        return target == node.val || find(node.left, target) || find(node.right, target);
    }

}

复杂度分析

时间

find我们遍历整个树的节点，复杂度O(n)，n表示树节点数。

LC时间效率只打败了15%的用户，迫使我去研究了下题解区大佬们的思路。

空间

额外维护了一个树结构，空间复杂度O(n)。

logn跳转查找

思路

解法1时间效率表现太差了。看了看题解区，发现了logn效率的解法。

我们的解法1没有利用上左右节点奇偶特征，利用这个特征，可以完成二分的逻辑。

  • 初始化时，其实无需维护一棵干净的树，这样也节省了初始化常驻空间的开销；
  • 查找时，根据入参target，我们根据奇偶性，可以判断当前节点是父节点的左还是右节点，将这个左右跳转路径保存下来，接着查找这个logn路径即可！

此方法实际运行效果真的好！思路值得学习！

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

static class FindElements2 {

    TreeNode root;

    public FindElements2(TreeNode root) {
        this.root = root;
    }

    public boolean find(int target) {
        if (target < 0) return false;

        // 根据左右子节点奇偶性，构建查询路径（下一步向左还是向右跳）
        // true表示当前节点为父节点的右节点（child=2*parent+2），反之亦然
        Deque<Boolean> stk = new LinkedList<>();
        // target数字逐步除以二，回到父节点的值
        while (target != 0) {
            boolean isEven = target % 2 == 0;
            stk.push(isEven);
            target = isEven ? (target - 2) / 2 : (target - 1) / 2;
        }

        TreeNode curr = root;
        while (!stk.isEmpty()) {
            if (curr == null) {
                return false;
            }
            Boolean rightChild = stk.pop();
            curr = rightChild ? curr.right : curr.left;
        }
        // 当前节点非null，说明能找到，否则不能
        return curr != null;
    }
}

复杂度分析

时间

find跳转时，每次可跳过一半子树节点，时间复杂度O(logn)，n表示树节点数。

空间

常驻无空间开销，find时会持有一个栈结构，方法执行结束后空间自然释放，空间复杂度O(logn)。