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

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

输入：
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]

[null,false,true]

FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // return False
findElements.find(2); // return True


输入：
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]

[null,true,true,false]

FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False


输入：
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]

[null,true,false,false,true]

FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True


• TreeNode.val == -1
• 二叉树的高度不超过 20
• 节点的总数在 [1, 10^4] 之间
• 调用 find() 的总次数在 [1, 10^4] 之间
• $0 <= target <= 10^6$

2、解题思路¶

• 使用DFS将所有节点生成出来，放入集合中
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class FindElements:

def __init__(self, root: TreeNode):
self.data_set = set()

def dfs(parent, node, direction):
if node:
if direction:
n = 2 * parent + 1
else:
n = 2 * parent + 2

dfs(n, node.left, 1)
dfs(n, node.right, 0)

if root: