泰州网站设计哪家好,上海三益建筑设计有限公司,注册一个小网站,千度seo今天是2024年3月12日#xff0c;可能是因为今天是植树节的原因#xff0c;今天的每日一题是二叉树#x1f64f;#x1f3fb;
在受污染的二叉树中查找元素
题目描述
给出一个满足下述规则的二叉树#xff1a;
root.val 0
如果 treeNode.val x 且 treeNode.left ! n…今天是2024年3月12日可能是因为今天是植树节的原因今天的每日一题是二叉树
在受污染的二叉树中查找元素
题目描述
给出一个满足下述规则的二叉树
root.val 0
如果 treeNode.val x 且 treeNode.left ! null那么 treeNode.left.val 2 * x 1
如果 treeNode.val x 且 treeNode.right ! null那么 treeNode.right.val 2 * x 2
现在这个二叉树受到「污染」所有的 treeNode.val 都变成了 -1。
请你先还原二叉树然后实现 FindElements 类
FindElements(TreeNode* root) 用受污染的二叉树初始化对象你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。 示例 1 输入
[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 示例 2 输入
[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 示例 3 输入
[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 解题思路
利用哈希表
还原二叉树 从 root 出发先将 root 的 val 还原为 0再从 root 出发 dfs 这棵树还原二叉树
递归左儿子传入 val⋅21。递归右儿子传入 val⋅22。 递归的同时把还原后的节点值加到一个哈希表中。
class FindElements {private SetInteger valSet new HashSet();// 还原根节点并dfs二叉树public FindElements(TreeNode root) {dfs(root, 0);}// 还原二叉树并将val存入哈希表private void dfs(TreeNode node, int val) {if (node null) {return;}valSet.add(val);dfs(node.left, val * 2 1);dfs(node.right, val * 2 2);}
}再利用哈希表的 contains 方法查找哈希表中知否包含 target 值。
class FindElements {private SetInteger valSet new HashSet();// 还原根节点并dfs二叉树public FindElements(TreeNode root) {dfs(root, 0);}// 查找是否包含targetpublic boolean find(int target) {return valSet.contains(target);}// 还原二叉树并将val存入哈希表private void dfs(TreeNode node, int val) {if (node null) {return;}valSet.add(val);dfs(node.left, val * 2 1);dfs(node.right, val * 2 2);}
} 到这里这个算法问题就算解决啦解决这个问题的方法有很多种我也只是选了一种我自己了解的记录下来大家可以自己去尝试不同的解法比如力扣上一位大佬写出了用位运算的二进制解法。 算法复杂度分析 时间复杂度 构造函数的时间复杂度为 O(n) 函数的时间复杂度为 O(1)。 空间复杂度O(n)。 n为树的节点数空间复杂度主要为哈希表占用的空间。 写在最后植树节快乐~天天快乐~多种树~
