题解 | 判断是不是平衡二叉树

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <ios>
class Solution {
public:
    bool res = true;
    int dfs(TreeNode* root){        // 返回深度
        if(!root)
            return 0;
        int left_dep = dfs(root->left);
        int right_dep = dfs(root->right);
        if(abs(left_dep-right_dep)>1)
            res = false;
        return max(left_dep, right_dep) + 1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int dep = dfs(pRoot);
        return res;
    }
};

思路：

step1：在最外面定义一个bool res用来记录有没出现不平衡情况；初始为true，只要有一个子树不平衡，则置为false；

step2：dfs，其返回最大深度。截止条件：树为空，则深度为0。

step3：dfs(left), dfs(right)，如果二者结果差>1，则res=false。返回二者结果中最大的那个+1，用来表示该节点的最大深度。