位运算，LeetCode 1261. 在受污染的二叉树中查找元素

本文主要是介绍位运算，LeetCode 1261. 在受污染的二叉树中查找元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

给出一个满足下述规则的二叉树：

1. root.val == 0
2. 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
3. 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

• FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
• bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

2、接口描述

​

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class FindElements {
public:FindElements(TreeNode* root):rt(root) {}bool find(int target) {}
};/*** Your FindElements object will be instantiated and called as such:* FindElements* obj = new FindElements(root);* bool param_1 = obj->find(target);*/

3、原题链接

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

---

二、解题报告

1、思路分析

平时写线段树都是按照根节点为1，左子树为1 << 1，右子树为1 << 1 | 1……这样发现所有节点左孩子编号都是偶数，右孩子都是奇数

那么我们将树中节点值都+1，同样满足这个性质

那么我们把target+1后，从高位1的下一个位置开始判断（因为高位1来自于根节点1向左移位）

然后如果为1就往右走，0就往左走

如果节点为空了，就返回false

2、复杂度

时间复杂度： O(min(log target, h))空间复杂度：O(1)

3、代码详解

​C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class FindElements {
public:TreeNode* rt;FindElements(TreeNode* root):rt(root) {}bool find(int target) {++target;TreeNode* cur = rt;for(int i = 30 - __builtin_clz(target); i >= 0; i--){if(target >> i & 1) cur = cur -> right;else cur = cur -> left;if(!cur) return false;}return true;}
};/*** Your FindElements object will be instantiated and called as such:* FindElements* obj = new FindElements(root);* bool param_1 = obj->find(target);*/

python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class FindElements:def __init__(self, root: Optional[TreeNode]):self.root = rootdef find(self, target: int) -> bool:cur = self.roottarget += 1for i in range(target.bit_length() - 2, -1, -1):cur = cur.right if target >> i & 1 else cur.leftif cur is None:return Falsereturn True# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)

这篇关于位运算，LeetCode 1261. 在受污染的二叉树中查找元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---