Find Elements in a Contaminated Binary Tree — LeetCode 1261 Python Solution

The problem

Given a binary tree with the following rules: root.val == 0 For any treeNode: If treeNode.val has a value x and treeNode.left != null, then treeNode.left.val == 2 * x + 1 If treeNode.val has a value 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.

Example

Input

["FindElements","find","find"]

Output

[null,false,true]

Explanation

FindElements findElements = new FindElements([-1,null,-1]);

Python solution

# 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]):
        def dfs(root: Optional[TreeNode]):
            self.s.add(root.val)
            if root.left:
                root.left.val = root.val * 2 + 1
                dfs(root.left)
            if root.right:
                root.right.val = root.val * 2 + 2
                dfs(root.right)

        root.val = 0
        self.s = set()
        dfs(root)

    def find(self, target: int) -> bool:
        return target in self.s


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

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1261. Find Elements in a Contaminated Binary Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems