首页 > 其他 > 详细

【leetcode】1261. Find Elements in a Contaminated Binary Tree

时间:2019-11-20 12:18:52      阅读:68      评论:0      收藏:0      [点我收藏+]

题目如下:

Given a binary tree with the following rules:

  1. root.val == 0
  2. If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
  3. If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

You need to first recover the binary tree and then implement the FindElements class:

  • FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
  • bool find(int target) Return if the target value exists in the recovered binary tree.

Example 1:

技术分享图片

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]
Explanation
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True 

Example 2:

技术分享图片

Input
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output
[null,true,true,false]
Explanation
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

Example 3:

技术分享图片

Input
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output
[null,true,false,false,true]
Explanation
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

Constraints:

  • TreeNode.val == -1
  • The height of the binary tree is less than or equal to 20
  • The total number of nodes is between [1, 10^4]
  • Total calls of find() is between [1, 10^4]
  • 0 <= target <= 10^6

解题思路:题目很简单,先把树恢复,然后判断值是否存在。

代码如下:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class FindElements(object):
    dic = {}
    root = None
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.dic = {}
        self.root = root
        def recursive(node,node_val):
            node.val = node_val
            self.dic[node.val] = 1
            if node.left != None:
                recursive(node.left,node.val*2+1)
            if node.right != None:
                recursive(node.right,node.val*2+2)
        recursive(self.root,0)
        

    def find(self, target):
        """
        :type target: int
        :rtype: bool
        """
        return target in self.dic
        


# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)

 

【leetcode】1261. Find Elements in a Contaminated Binary Tree

原文:https://www.cnblogs.com/seyjs/p/11896193.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!