current position：Home>leetcode 1261. Find Elements in a Contaminated Binary Tree（python）
leetcode 1261. Find Elements in a Contaminated Binary Tree（python）
20220129 15:45:08 【Wang Daya】
This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .
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 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 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 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 code
analysis
According to the meaning , Given a tree , But you can only see the structure of the tree , Because the tree is polluted, the values of all nodes are 1 , However, the value of the node can be reproduced and restored , That is, the root node is 0 , The value of the left node is twice the value of its parent node plus one , The value of the right node is twice the value of its parent node . The title requires us to use __init__ Function first restores the tree , And then use find Function judgement target Whether it exists in the tree .
The idea is simple , Is to use recursion to directly calculate the values of the nodes of the tree and store them in a list , And then determine target Whether it is in the list . In fact, this problem looks complex , It's actually 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 code
Running results
Runtime: 622 ms, faster than 6.67% of Python online submissions for Find Elements in a Contaminated Binary Tree.
Memory Usage: 19.2 MB, less than 76.67% of Python online submissions for Find Elements in a Contaminated Binary Tree.
Copy code
analysis
You can also use queues to solve this problem , The process of building the tree is similar to the above process , I won't repeat .
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 code
Running results
Runtime: 143 ms, faster than 33.33% of Python online submissions for Find Elements in a Contaminated Binary Tree.
Memory Usage: 19.7 MB, less than 13.33% of Python online submissions for Find Elements in a Contaminated Binary Tree.
Copy code
Original link ：leetcode.com/problems/fi…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201291545062910.html
The sidebar is recommended
 [Python introduction project] use Python to generate QR code
 Compile D + +, and use d to call C from python
 Quickly build Django blog based on function calculation
 Python collects and monitors system data  psutil
 Quickly build Django blog based on function calculation
 Python interface test unittest usage details
 Implementation of toplevel design pattern in Python
 You can easily get started with Excel. Python data analysis package pandas (VII): breakdown
 Python simulation random coin toss (non optimized version)
 Python tiktok 5000+ V, and found that everyone love this video.
guess what you like

Using linear systems in python with scipy.linalg

Using linear systems in python with scipy.linalg

Together with Python to do a license plate automatic recognition system, fun and practical!

You can easily get started with Excel. Python data analysis package pandas (XI): segment matching

Advanced practical case: Javascript confusion of Python anti crawling

Using linear systems in python with scipy.linalg

Fast power modulus Python implementation of large numbers

Quickly build Django blog based on function calculation

This paper clarifies the chaotic switching operation and elegant derivation of Python

You can easily get started with Excel pandas (I): filtering function
Random recommended
 You can easily get started with Excel. Python data analysis package pandas (II): advanced filtering (I)
 You can easily get started with Excel. Python data analysis package pandas (2): advanced filtering (2)
 You can easily get started with Excel. Python data analysis package pandas (3): making score bar
 Test Development: self study Dubbo + Python experience summary and sharing
 How does Python correctly call jar package encryption to get the encrypted value?
 Python 3 interview question: give an array. If there is 0 in the array, add a 0 after 0, and the overall array length remains the same
 Python simple Snake game (single player mode)
 Using linear systems in python with scipy.linalg
 Python executes functions and even code through strings! Come and understand the operation of such a top!
 Decoding the verification code of Taobao slider with Python + selenium, the road of information security
 [Python introduction project] use Python to generate QR code
 Vanessa basks in her photos and gets caught up in the golden python. There are highlights in the accompanying text. She can't forget Kobe after all
 [windows] Python installation pyteseract
 [introduction to Python project] create bar chart animation in Python
 Fundamentals of Python I
 Python series tutorials 116
 Python code reading (chapter 35): fully (deeply) expand nested lists
 Practical series 1 ️⃣ Wechat applet automatic testing practice (with Python source code)
 Python Basics: do you know how to use lists?
 Solution of no Python 3.9 installation was detected when uninstalling Python
 [Python homework] coupling network information dissemination
 [common links of Python & Python]
 [Python development tool tkinterdiesigner]: example: develop stock monitoring alarm using Tkinter desinger
 [Python development tool Tkinter designer]: Lecture 2: introduction to Tkinter designer's example project
 [Python development tool Tkinter designer]: Lecture 1: introduction to the basic functions of Tkinter Designer
 [introduction to Python tutorial] use Python 3 to teach you how to extract any HTML main content
 Python socket implements UDP server and client
 Python socket implements TCP server and client
 [algorithm learning] 1486 Array XOR operation (Java / C / C + + / Python / go / trust)
 leetcode 1974. Minimum Time to Type Word Using Special Typewriter（python）
 The mobile phone uses Python to operate picture files
 [learning notes] Python exception handling try except...
 Two methods of using pandas to read poorly structured excel. You're welcome to take them away
 Python sum (): the summation method of Python
 Practical experience sharing: use pyo3 to build your Python module
 Using Python to realize multitasking process