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

思路

👨‍🏫 灵神题解

💖 二进制

• 时间复杂度：初始化为 $O(1)$；find 为 $O(min(h,lo{g}_{2}target)$，其中 h 为二叉树的高度
• 空间复杂度：$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)$，其中 $n$ 为二叉树的节点个数。find 为 $O(1)$
• 空间复杂度：$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(nm)$
• 空间复杂度: $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);*/