LeetCode 1261. 在受污染的二叉树中查找元素 ,对比树的DFS
常规解法、logn
优化解法。
1261. 在受污染的二叉树中查找元素#
https://leetcode.cn/problems/find-elements-in-a-contaminated-binary-tree/
Given a binary tree with the following rules:
- root.val == 0
- If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
- 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)
。