题解 | #平衡二叉树#
平衡二叉树
http://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
递归记录树高以及是否为平衡二叉树。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
def dfs(root):
if not root:
return (0, True)
lefth, left = dfs(root.left)
righth, right = dfs(root.right)
return (1+max(lefth, righth) ,left and right and abs(lefth-righth)<=1)
return dfs(pRoot)[1]