Problem: 1261. 在受污染的二叉树中查找元素
思路
👨🏫 灵神题解
💖 二进制
- 时间复杂度:初始化为 O ( 1 ) O(1) O(1);find 为 O ( m i n ( h , l o g 2 t a r g e t ) O(min(h,log_2target) O(min(h,log2target),其中 h 为二叉树的高度
- 空间复杂度: O ( 1 ) O(1) O(1)
class FindElements {
private TreeNode root;
public FindElements(TreeNode root) {
this.root = root;
}
public boolean find(int target) {
target++;
TreeNode cur = root; // 从根节点出发
for (int i = 30 - Integer.numberOfLeadingZeros(target); i >= 0; i--) { // 从次高位开始枚举
int bit = (target >> i) & 1; // target 第 i 位的比特值
cur = bit == 0 ? cur.left : cur.right;
if (cur == null) { // 走到空节点,说明 target 不在二叉树中
return false;
}
}
return true; // 没有走到空节点,说明 target 在二叉树中
}
}
💖 哈希表
复杂度分析
- 时间复杂度:初始化为 O ( n ) O(n) O(n),其中 n n n 为二叉树的节点个数。find 为 O ( 1 ) O(1) O(1)
- 空间复杂度: O ( n ) O(n) O(n)
class FindElements {
private final Set<Integer> s = new HashSet<>();
public FindElements(TreeNode root) {
dfs(root, 0);
}
public boolean find(int target) {
return s.contains(target);
}
private void dfs(TreeNode node, int val) {
if (node == null) {
return;
}
s.add(val);
dfs(node.left, val * 2 + 1);
dfs(node.right, val * 2 + 2);
}
}
💖 暴力版
- 时间复杂度:
- 转换: O ( n ) O(n) O(n)
- 查找: O ( n m ) O(nm) O(nm)
- 空间复杂度: O ( n ) O(n) O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class FindElements {
TreeNode r;
public FindElements(TreeNode root) {
r = root;
if(root == null) return;
root.val = 0;
dfs(root);
}
void dfs(TreeNode cur)
{
if(cur == null)
return;
if(cur.left != null)
{
cur.left.val = cur.val * 2 + 1;
dfs(cur.left);
}
if(cur.right != null)
{
cur.right.val = cur.val * 2 + 2;
dfs(cur.right);
}
}
boolean f(TreeNode cur, int x)
{
if(cur == null)
return false;
if(cur.val == x)
return true;
if(f(cur.left,x) || f(cur.right,x))
return true;
return false;
}
public boolean find(int target) {
return f(r,target);
}
}
/**
* Your FindElements object will be instantiated and called as such:
* FindElements obj = new FindElements(root);
* boolean param_1 = obj.find(target);
*/