题目描述

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

示例 1:

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

    3/ \9  20/  \15   7

返回 true 。

示例 2:

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

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

返回 false 。

解题思路与代码

自底向上的递归

为什么说是自底而上的递归呢？首先，我们先递归到达二叉树叶子节点，由叶子节点开始做逻辑判断。然后逐步向上返回判断的结果，最后在二叉树的顶部，我们就根据底部传来的结果去做出判断，到达是返回false，还是true。

那我们判断的逻辑是什么呢？
首先我们肯定是要去写递归函数的。由于主函数是一个bool类型的函数，它是要返回true，或false。而我想的逻辑是判断子节点的高度差，那返回的肯定是个int。所以不能在主函数里写递归，要另写一个递归函数。

我们在主函数外写的递归函数的返回类型是int。然后参数呢，是一个TreeNode* 的类型。确定了递归函数的返回类型，与要传入的参数。我们来想想如何结束每一层的递归。那我们会传入一个节点。我们要拿这个节点的左右子节点去递归判断。首当其冲的结束条件就是这个节点它不能为nullptr，如果为空，就直接返回0。

为了减少递归的次数，我们再补充一条结束条件。如果该节点的左右子节点都为空，那我们就返回1。

写完了结束条件后，我们现在可以来仔细想想递归的单层逻辑怎么去写了。首先，设置两个int类型的变量，left，right。
它们分别将传入节点的左右子节点拿去递归。所以 left = root->left ,right = root->right 。

那逻辑其实就是从判读每个节点的左右子树的高度差嘛，如果高度差大于1，我们就直接返回 -1 ，这就是最重要的逻辑
那代码表示，就是在left与right处都进行判断，才能达到这个效果。

最后，如果值都正常的话，返回 1 + max(left,right)就行了。

具体的实现，请看下面的代码：

/*** 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 == nullptr) return true;int left = height(root->left);int right = height(root->right);if(left == -1 || right == -1) return false;if(abs(left - right) > 1) return false;return true;}int height (TreeNode* root){if(root == nullptr) return 0;if(root->left == nullptr && root->right == nullptr) return 1;int left = height(root->left);if(left == -1) return -1;int right = height(root->right);if(right == -1) return -1;if(abs(left - right) > 1) return -1;return 1 + max(left,right);}};

在这里插入图片描述

复杂度分析

时间复杂度：O(n),其中n是二叉树的节点个数。最坏情况下，我们需要遍历完整个二叉树所有节点一遍，才能得出最终的结论。所以时间复杂度是O(n)。

空间复杂度：O(m),其中m是二叉树的高度。也就是我们需要递归的层数。

从顶部向下的递归

那为什么要叫从顶向下的递归呢？这是因为，我们从顶部就开始做运算。一遍一遍的向叶子节点去做递归。等到叶子节点的图中，或到叶子节点了，就会出现结果。我们再将结果一层层的返回出来。由于计算是从上至下的，所以叫做从顶向下的递归。

这边直接给出代码吧，我自己就不深究这种做法了，因为这种做法的时间复杂度为O(n2),比我自己的代码要差很多。

这里贴出具体的代码：

class Solution {
public:int height(TreeNode* root) {if (root == NULL) {return 0;} else {return max(height(root->left), height(root->right)) + 1;}}bool isBalanced(TreeNode* root) {if (root == NULL) {return true;} else {return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);}}
};