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)