题目

输出一棵节点数为 n 二叉树，判断该二叉树是否是均衡二叉树。
在这里，咱们只须要思考其平衡性，不须要思考其是不是排序二叉树
均衡二叉树（Balanced Binary Tree），具备以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵均衡二叉树。
样例解释：

样例二叉树如图，为一颗均衡二叉树
注：咱们约定空树是均衡二叉树。

数据范畴：n≤100,树上节点的val值满足 0≤n≤1000

要求：空间复杂度O(1)，工夫复杂度 O(n)

参数阐明：二叉树类，二叉树序列化是通过按层遍历,#代表这这个节点为空节点，举个例子：

  1 / \2   3   /  4

以上二叉树会被序列化为 {1,2,3,#,#,4}

示例1

输出：{1,2,3,4,5,6,7}返回值：true

示例2

输出：{}返回值：true

思路

  • 用递归的办法计算每个节点的深度（节点深度=左右子树深度最大值+1）。
  • 判断节点左右子树深度的差值是否大于1，大于1则不是均衡的。
  • 同时递归判断左右子树也得是均衡的。
  • 这个算法还有一个优化的思路是：递归的函数判断是否均衡的同时返回节点的深度（解法略）。

解答代码

/** * struct TreeNode { *    int val; *    struct TreeNode *left; *    struct TreeNode *right; *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */#include <algorithm>class Solution {public:    /**     * @param pRoot TreeNode类      * @return bool布尔型     */    bool IsBalanced_Solution(TreeNode* pRoot) {        // write code here        if (pRoot == nullptr) {            return true;        }        auto left_depth = Depth(pRoot->left);        auto right_depth = Depth(pRoot->right);        // 左右子树深度相差大于1        if (left_depth - right_depth > 1 || right_depth - left_depth > 1) {            return false;        }        // 同时左右子树也都得是均衡二叉树        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);    }    int Depth(TreeNode* pRoot) {        if (pRoot == nullptr) {            return 0;        }        auto left_depth = Depth(pRoot->left);        auto right_depth = Depth(pRoot->right);        // 根的深度是子树最大深度+1        return max(left_depth+1, right_depth+1);    }};