手机网站建设哪/优化大师怎么提交作业

平衡二叉树

题目描述：

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

题目链接

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {if(root == null) return true;if(Math.abs(getHeight(root.left)-getHeight(root.right))<=1  // 对当前根节点的左右子树判断高度差绝对值是否超过一&& isBalanced(root.left) && isBalanced(root.right)) // 对每一个根节点递归判断左右子树是否平衡return true;else return false;}private int getHeight(TreeNode root){if(root == null) return 0;return Math.max(getHeight(root.left),getHeight(root.right))+1;}
}

按照题意即可，要判断二叉树是否为平衡二叉树，分别对左子树和右子树判断是否为平衡二叉树，而平衡二叉树和高度有关，故每次递归求解当前根节点的高度作为条件之一。详细请看代码，有疑问欢迎留言。