[DFS]110.|[DFS]110. Balanced Binary Tree
- 分类:Tree/DFS
- 时间复杂度: O(nlogn)/O(n)
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 depth of the two subtrees of every node never differ by more than 1.【[DFS]110.|[DFS]110. Balanced Binary Tree】Example 1:
Given the following tree
[3,9,20,null,null,15,7]
:3
/ \
920
/\
157
Return true.
Example 2:
Given the following tree
[1,2,2,3,3,null,null,4,4]
:1
/ \
22
/ \
33
/ \
44
Return false.
代码:
O(nlogn)方法:
# Definition for a binary tree node.
# class TreeNode:
#def __init__(self, x):
#self.val = x
#self.left = None
#self.right = Noneclass Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root==None:
return Trueh_left=self.height(root.left)
h_right=self.height(root.right)
return abs(h_left-h_right)<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)def height(self, root):
if root==None:
return 0
else:
return max(self.height(root.left),self.height(root.right))+1
O(n)方法:
# Definition for a binary tree node.
# class TreeNode:
#def __init__(self, x):
#self.val = x
#self.left = None
#self.right = Noneclass Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root==None:
return True
def height(root):
if root==None:
return 0
h_l=height(root.left)
h_r=height(root.right)
if h_l==-1 or h_r==-1 or abs(h_l-h_r)>1:
return -1
else:
return max(h_l,h_r)+1
return height(root)!=-1
讨论: 1.经典平衡2叉树,用DFS解(也是递归orz)
2.第一种O(nlogn)的方法好解释
3.第二种O(n)的方法是直接检测高度,当高度差>1的时候直接返回-1,直接返回-1到最终,速度快。
![[DFS]110.|[DFS]110. Balanced Binary Tree](https://img.it610.com/image/info10/af5bd3a87a4c40be88a5facb31de9ed0.jpg)
文章图片
110
推荐阅读
- 剑指|剑指 Offer 13. 机器人的运动范围(dfs,bfs)
- CentOS|CentOS 7.2搭建FastDFS 分布式文件系统,实现高可用集群
- HDFS读写数据流
- HDFS文件损坏解决方法
- 网络爬虫抓取图片并上传到fastdfs图片不完整问题解决
- 基础课|使用深度优先搜索(DFS)、广度优先搜索(BFS)、A* 搜索算法求解 (n^2 -1) 数码难题,耗时与内存占用(时空复杂度)对比(附((n^2 - 1) 数码问题控
- leetCode解题报告|leetCode解题报告之Palindrome Partitioning I,II(DFS,DP)
- 谈一谈动态规划和dfs
- DFS|使用DFS(深搜)遍历所有的序列所有的子组合(子序列)(排列组合中的组合)
- 搜索技术|UVA10054 The Necklace——欧拉回路(DFS)