LeetCode 110. Balanced Binary Tree

题目

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.

分析

判断一个二叉树是不是平衡二叉树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
# recursively
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.dfs(root) != -1
def dfs(self, root):
if root is None:
return 0
left = self.dfs(root.left)
right = self.dfs(root.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
# Iterative, based on postorder traversal:
def isBalanced1(self, root):
stack, node, last, depths = [], root, None, {}
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack[-1]
if not node.right or last == node.right:
node = stack.pop()
left, right = depths.get(node.left, 0), depths.get(node.right, 0)
if abs(left - right) > 1: return False
depths[node] = 1 + max(left, right)
last = node
node = None
else:
node = node.right
return True

点评

递归版本的比较好理解,每次递归 dfs 传递子树根节点,返回的是对应子树的最大高度,如果出现不平衡的情况,一定会发现某次的 left-right 值大于 1
迭代版本??????