输入一棵二叉树,判断该二叉树是否是平衡二叉树
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
===========Python===========
# -*- 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 if not pRoot: return True return abs(self.depth(pRoot.left) - self.depth(pRoot.right)) <= 1 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right) def depth(self, root): if not root: return 0 return max(self.depth(root.left),self.depth(root.right)) + 1
================Java===============
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if (root == null) { return true; } return Math.abs(depth(root.left) - depth(root.right)) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right); } public int depth(TreeNode p) { if (p == null) { return 0; } return Math.max(depth(p.left), depth(p.right)) + 1; } }