current position:Home>leetcode 110. Balanced Binary Tree(python)
leetcode 110. Balanced Binary Tree(python)
2022-01-30 04:45:36 【Wang Daya】
Little knowledge , Great challenge ! This article is participating in “ A programmer must have a little knowledge ” Creative activities .
describe
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Copy code
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Copy code
Example 3:
Input: root = []
Output: true
Copy code
Note:
The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 104
Copy code
analysis
According to the meaning , A binary tree is given , Check whether the binary tree is highly balanced .
A highly balanced binary tree , It means that the height difference between the left subtree and the right subtree of each node is no more than 1.
This question is actually the same as leetcode 108. Convert Sorted Array to Binary Search Tree The contents of the investigation are the same , It's all about calculating the depth of the tree , I can do that problem, and this problem is similar .
Define a function depth Used to calculate the height of a node , If the node is empty, it will directly return 0 . If it is not empty, continue to drill down into its left and right subtrees to calculate the height of the current node .
Define a function isBalanced It is used to judge whether the current node is a balanced binary tree , adopt depth The height of its subtree can be obtained l and r , Then compare whether the height difference between the left and right subtrees of the current node is less than 2 And the left and right subtrees are also highly balanced binary trees .
answer
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:return True
def depth(root):
if not root:return 0
return max(depth(root.left), depth(root.right)) + 1
l = depth(root.left)
r = depth(root.right)
return abs(l-r)<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)
Copy code
Running results
Runtime: 56 ms, faster than 48.18% of Python online submissions for Balanced Binary Tree.
Memory Usage: 17.6 MB, less than 88.07% of Python online submissions for Balanced Binary Tree.
Copy code
Similar topics
Original link :leetcode.com/problems/ba…
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/202201300445350892.html
The sidebar is recommended
- Python collects and monitors system data -- psutil
- Python chat room (Tkinter writing interface, streaming, socket to realize private chat, group chat, check chat records, Mysql to store data)
- Learning this Python library can reduce at least 100 lines of code
- leetcode 67. Add Binary(python)
- Regular re parameter replacement of Python 3 interface automation test framework
- V. pandas based on Python
- Only 15 lines of code is needed for face detection! (using Python and openCV)
- [Python crawler Sao operation] you can crawl Sirius cinema movies without paying
- leetcode 69. Sqrt(x)(python)
- Teach you to read the source code of Cpython (I)
guess what you like
-
Snowball learning started in the fourth quarter of Python. One needs three meals. I have a new understanding of Python functional programming, process-oriented, object-oriented and functional
-
leetcode 88. Merge Sorted Array(python)
-
Don't you know more about a python library before the end of 2021?
-
Python crawler web page parsing artifact XPath quick start teaching!!!
-
Use Python and OpenCV to watermark the image
-
String and related methods of Python data type introduction
-
Heapq module of Python module
-
Introduction to beautiful soup of Python crawler weapon, detailed explanation, actual combat summary!!!
-
Event loop of Python collaboration series
-
Django docking pin login system
Random recommended
- [recalling the 1970s] using Python to repair the wonderful memories of parents' generation, black-and-white photos become color photos
- You used to know Python advanced
- Pyinstaller package Python project
- 2021 IEEE programming language rankings: Python tops the list!
- Implementation of Python automatic test control
- Python advanced: [Baidu translation reverse] graphic and video teaching!!!
- Do you know the fuzzy semantics in Python syntax?
- [Python from introduction to mastery] (XXVII) learn more about pilot!
- Playing excel office automation with Python
- Some applications of heapq module of Python module
- Python and go languages are so popular, which is more suitable for you?
- Python practical skills task segmentation
- Python simulated Login, numpy module, python simulated epidemic spread
- Python opencv contour discovery function based on image edge extraction
- Application of Hoff circle detection in Python opencv
- Python reptile test ox knife (I)
- Day 1: learn the Django framework of Python development
- django -- minio_ S3 file storage service
- [algorithm learning] 02.03 Delete intermediate nodes (Java / C / C + + / Python / go)
- Similarities and differences of five pandas combinatorial functions
- Learning in Python + opencv -- extracting corners
- Python beginner's eighth day ()
- Necessary knowledge of Python: take you to learn regular expressions from zero
- Get your girlfriend's chat records with Python and solve the paranoia with one move
- My new book "Python 3 web crawler development practice (Second Edition)" has been recommended by the father of Python!
- From zero to familiarity, it will take you to master the use of Python len() function
- Python type hint type annotation guide
- leetcode 108. Convert Sorted Array to Binary Search Tree(python)
- For the geometric transformation of Python OpenCV image, let's first talk about the extraordinary resize function
- leetcode 701. Insert into a Binary Search Tree (python)
- For another 3 days, I sorted out 80 Python datetime examples, which must be collected!
- Python crawler actual combat | using multithreading to crawl lol HD Wallpaper
- Complete a python game in 28 minutes, "customer service play over the president card"
- The universal Python praise machine (commonly known as the brushing machine) in the whole network. Do you want to know the principle? After reading this article, you can write one yourself
- How does Python compare file differences between two paths
- Common OS operations for Python
- [Python data structure series] linear table - explanation of knowledge points + code implementation
- How Python parses web pages using BS4
- How do Python Network requests pass parameters
- Python core programming - decorator