Leetcode 1261. Find Elements in a Contaminated Binary Tree解题报告(python)

1261. Find Elements in a Contaminated Binary Tree

1261. Find Elements in a Contaminated Binary Tree solution

题目描述

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.
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.

解析

解题思路比较简单，题目也很好理解。首先，将一个被污染的树按照题目中给出的赋值要求进行还原，然后再还原的树中查询target。使用set（）函数可以是代码更简洁。

// An highlighted block
class FindElements:

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.tree = set()
        def preorder(root, val):
            if root:
                root.val = val
                self.tree.add(root.val)
                preorder(root.left, (root.val*2) + 1)
                preorder(root.right, (root.val*2) + 2)
                
        preorder(root, 0)


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

Reference

https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/discuss/431262/Python-Preorder-%2B-Set