算法题--判断一棵二叉树是否平衡
2020-04-29 本文已影响0人
岁月如歌2020
image.png
0. 链接
1. 题目
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:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree
[1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
2. 思路1: 先通过遍历设置每个节点作为根节点的子树的深度+再遍历判断每个节点的左右子树深度是否相差超过1
时间复杂度 O(N)
空间复杂度 O(logN)
3. 代码
# coding:utf8
# 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 Solution:
def isBalanced(self, root: TreeNode) -> bool:
def depth(node):
if node.left is None and node.right is None:
node.val = 1
return node.val
elif node.left is not None and node.right is not None:
node.val = 1 + max(depth(node.left), depth(node.right))
return node.val
elif node.left is not None:
node.val = 1 + depth(node.left)
return node.val
elif node.right is not None:
node.val = 1 + depth(node.right)
return node.val
else:
return 0
def check(node):
left_depth = node.left.val if node.left is not None else 0
right_depth = node.right.val if node.right is not None else 0
if abs(right_depth - left_depth) > 1:
return False
else:
left_balanced = check(node.left) if node.left is not None else True
right_balanced = check(node.right) if node.right is not None else True
return left_balanced and right_balanced
depth(root)
return check(root)
def print_tree(root):
def traverse(node, results):
results.append(node.val)
if node.left is not None:
traverse(node.left, results)
else:
results.append(None)
if node.right is not None:
traverse(node.right, results)
else:
results.append(None)
array = list()
if root is not None:
traverse(root, array)
print(array)
solution = Solution()
root1 = node = TreeNode(3)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)
print(solution.isBalanced(root1))
print_tree(root1)
root2 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(2)
node.left.left = TreeNode(3)
node.left.right = TreeNode(3)
node.left.left.left = TreeNode(4)
node.left.right.right = TreeNode(4)
print(solution.isBalanced(root2))
print_tree(root2)
root3 = node = TreeNode(1)
node.right = TreeNode(2)
node.right.right = TreeNode(3)
print(solution.isBalanced(root3))
print_tree(root3)
输出结果
True
[3, 1, None, None, 2, 1, None, None, 1, None, None]
False
[4, 3, 2, 1, None, None, None, 2, None, 1, None, None, 1, None, None]
False
[3, None, 2, None, 1, None, None]
4. 结果
image.png
5. 方法2: DFS
- 过程
- 思想同样是从底部到高层计算每个节点距离最底层的高度
- 一旦发现左右子树高度差超过1, 则此节点的计算结果返回-1
- 一旦发现左右子树有一个的高度为-1, 则当前节点的计算结果返回-1
- 这样就不用存储中间结果, 而直接可以算出最后结果
- 复杂度
- 时间复杂度
O(n) - 空间复杂度
O(logN)
6. 代码
class Solution1:
def isBalanced(self, root: TreeNode) -> bool:
def depth(node):
if node is None:
return 0
left_depth = depth(node.left) if node.left is not None else 1
if left_depth == -1:
return -1
right_depth = depth(node.right) if node.right is not None else 1
if right_depth == -1:
return -1
if abs(right_depth - left_depth) > 1:
return -1
return 1 + max(right_depth, left_depth)
return depth(root) != -1
def print_tree(root):
def traverse(node, results):
results.append(node.val)
if node.left is not None:
traverse(node.left, results)
else:
results.append(None)
if node.right is not None:
traverse(node.right, results)
else:
results.append(None)
array = list()
if root is not None:
traverse(root, array)
print(array)
solution = Solution1()
root1 = node = TreeNode(3)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)
print(solution.isBalanced(root1))
print_tree(root1)
root2 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(2)
node.left.left = TreeNode(3)
node.left.right = TreeNode(3)
node.left.left.left = TreeNode(4)
node.left.right.right = TreeNode(4)
print(solution.isBalanced(root2))
print_tree(root2)
root3 = node = TreeNode(1)
node.right = TreeNode(2)
node.right.right = TreeNode(3)
print(solution.isBalanced(root3))
print_tree(root3)
输出结果
True
[3, 9, None, None, 20, 15, None, None, 7, None, None]
False
[1, 2, 3, 4, None, None, None, 3, None, 4, None, None, 2, None, None]
False
[1, None, 2, None, 3, None, None]
7. 结果
image.png
