题目分析

平衡二叉树指的是左右孩子的深度相差最多为1，这个条件就告诉了我们解法。为了练习C++语言，在今后一段时间内我就用C++写代码，小伙伴要做的事情不是关注于语言，而是关注算法本身，要深刻理解语言只是一门表达方式，只要思路正确，哪一种语言都可以解答。

哈希表

我们可以求得每一个节点的高度放在哈希表中，然后再次遍历这棵树，求每个节点的左右孩子高度之差是否都小于等于1即可。

代码难度较小，也容易想到，算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    map<TreeNode*, int> m;

    bool isBalanced(TreeNode* root) {
        m.clear();
        subQuestion(root);
        for (auto au : m) {
            if (abs(subQuestion(au.first->left) - subQuestion(au.first->right)) > 1) {
                return false;
            }
        }
        return true;
    }

    int subQuestion(TreeNode* node) {
        if (!node) {
            return 0;
        }
        if (!m.count(node)) {
            int left = subQuestion(node->left) + 1;
            int right = subQuestion(node->right) + 1;
            m[node] = max(left, right);
        }
        return m[node];
    }
};

递归

在哈希表的方法中，我们使用了哈希表，而且遍历了树结构两次。虽然时间复杂度仍是$O(n)$没有变化，但是可不可以寻找一种更优的解决方案呢？

我们可以自底向上进行递归，如果左右孩子的高度已知，那么就可以判断该节点是否满足条件。我们如何通过函数得到int类型的左右孩子高度和bool类型的该节点是否是平衡树呢？在我们的认识中，Python语言可以一次性返回多个不同类型的对象，但是其他语言怎么做呢？

在C++语言中，有一个其他语言无法比拟的优势——引用，我们将左右孩子的高度作为引用传入函数中，在函数中进行修改，那么就不需要返回int类型。

思路是：我们先定义根节点的高度为depth，然后传入函数subQuestion中，在函数中创建左右孩子的高度left和right，在判断左右孩子是否是平衡树时进行赋值。当左右孩子都是平衡树的时候，left和right已经被赋值了，计算left和right是否满足之差小于等于1，如果是则根节点的高度depth = max(left, right) + 1。

这种方法是这个题目的最优解，思路巧妙，代码难度较大，算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    map<TreeNode*, int> m;

    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        int depth = 0;
        return subQuestion(root, depth);
    }

    bool subQuestion(TreeNode* node, int& pDepth) {
        if (!node) {
            pDepth = 0;
            return true;
        }
        int left = 0, right = 0;
        if (subQuestion(node->left, left) && subQuestion(node->right, right)) {
            if (abs(left - right) <= 1) {
                pDepth = max(left, right) + 1;
                return true;
            }
        }
        return false;
    }
};

刷题总结

这个题目虽然标记为简单题，但是做起来并不简单，希望小伙伴们多加练习。而且我的建议是小伙伴们不能仅仅局限于一门语言之中，对于程序员来说，必须要掌握一门编译型语言和一门脚本语言，不能认为算法就不用关心语言本身，我认为这是不正确的，在编译型语言中，我首推C++，这是一门永远不会过时的语言，在学校中觉得Python就足够了，但是一旦进入到真正的工作中去，尤其是一些开发岗位，Python的需求还是很少的。