This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

describe

Given a binary tree with the following rules:

  • root.val == 0
  • If treeNode.val == x and treeNode.left ! = null, then treeNode.left.val == 2 * x + 1
  • 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.

Implement the FindElements class:

  • FindElements(TreeNode* root) Initializes the object with a contaminated binary tree and recovers it.
  • bool find(int target) Returns true 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 
Copy the code

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
Copy the code

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
Copy the code

Note:

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
Copy the code

parsing

The root node is 0, the value of the left node is two times the value of its parent, and the value of the right node is two times the value of its parent. We need to use __init__ to restore the tree, and then use find to determine if target is in the tree.

The idea is relatively simple, is to use recursion to directly calculate the value of the tree node in a list, and then determine whether target is in the list. The problem looks complicated, but actually it’s quite simple.

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class FindElements(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.vals = []
        def dfs(root, val):
            if not root:
                return
            self.vals.append(val)
            if root.left:
                dfs(root.left, val*2+1)
            if root.right:
                dfs(root.right, val*2+2)
        dfs(root, 0)


    def find(self, target):
        """
        :type target: int
        :rtype: bool
        """
        if target in self.vals:
            return True
        return False

        	      
		
Copy the code

The results

Runtime: 201 ms, faster than 6.67% of Python online submissions for Find Elements ina Contaminated Binary Tree. Memory Usage: 19.2 MB, less than 76.67% of Python online submissions for Find Elements ina Contaminated Binary Tree.Copy the code

parsing

You can also use queues to solve this problem. The tree building process is similar to the above and will not be described in detail.

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class FindElements(object):
    def __init__(self, root):
        self.A = set()
        queue = collections.deque([[root,0]])
        while queue:
            n,x = queue.popleft()
            self.A.add(x)
            if n.left:
                queue.append( [n.left  , 2*x+1] )
            if n.right:
                queue.append( [n.right , 2*x+2] )
                
    def find(self, target):
        return target in self.A
        
Copy the code

The results

Runtime: 136 ms, faster than 33.33% of Python online submissions for finding Elements ina Contaminated Binary Tree. Memory Usage: 19.7 MB, less than 13.33% of Python online submissions for Find Elements ina Contaminated Binary Tree.Copy the code

Original link: leetcode.com/problems/fi…

Your support is my biggest motivation