关于面试:每日一题判断是不是平衡二叉树

题目

输出一棵节点数为 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);
    }
};