本文共 1605 字，大约阅读时间需要 5 分钟。

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

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

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3   / \  9  20    /  \   15   7

返回 true 。

给定二叉树 [1,2,2,3,3,null,null,4,4]

1      / \     2   2    / \   3   3  / \ 4   4

返回 false 。

先求出节点左右子树的高度，然后判定是否为平衡树，如果是再递归左子树和右子树，不是，则直接返回。。

Java:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean isBalanced(TreeNode root) {        if(root==null)            return true;        int left=Height(root.left);        int right=Height(root.right);        if(Math.abs(left-right)>1)            return false;        else             return isBalanced(root.left)&&isBalanced(root.right);    }    private int Height (TreeNode root)    {        if(root==null)            return 0;        return Math.max(Height(root.left),Height(root.right))+1;    }}

C++:

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    bool isBalanced(TreeNode* root) {        if(root==NULL)            return true;        int left=Height(root->left);        int right=Height(root->right);        if(abs(left-right)>1)            return false;        else             return isBalanced(root->left)&&isBalanced(root->right);    }    int Height (TreeNode* root)    {        if(root==NULL)            return 0;        return max(Height(root->left),Height(root->right))+1;    }};

转载地址：http://vvaen.baihongyu.com/