怎么做企业官方网站/千锋教育培训机构地址

【题目描述】输入一棵二叉树，判断该二叉树是否是平衡二叉树。

注：注意平衡二叉树和平衡二叉搜索树的区分。有的书中混淆了两个概念。这里的平衡二叉树只关注是否平衡。

【解题思路】
//1. 平衡二叉树的定义是，满足任何一个节点的左右子树高度差都不大于1
//2. 递归处理。先判断根节点是否满足左右子树高度差的关系。然后判断左子树是否满足平衡二叉树的定义，然后是判断右子树。只有所有的节点都满足平衡二叉树的定义，则该树为平衡二叉树。
//3. 当前节点的高度也是一个递归的值，为其左子树和右子树高度中的最大值+1

public class Solution {public boolean IsBalanced_Solution(TreeNode root) {boolean flag=false;if(root !=null){int depthDiff = Math.abs(getDepth(root.left)-getDepth(root.right));if(depthDiff <= 1){flag = true;}flag = flag && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);}else{flag = true;}return flag;}//求当前节点的高度public int getDepth(TreeNode root){int max = 0;if(root != null){max = Math.max(getDepth(root.left), getDepth(root.right))+1;}return max;}
}