110. 平衡二叉树

力扣链接(简单)：https://leetcode.cn/problems/balanced-binary-tree

给定一个二叉树，判断它是否是 平衡二叉树。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

个人题解

递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 判断二叉树是否平衡，那就需要比较节点的高度
    int getHeight(TreeNode* node) {
        if(!node) return 0;

        int leftHeight = getHeight(node->left);
        // 子树不满足平衡二叉树
        if(leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        // 子树不满足平衡二叉树
        if(rightHeight == -1) return -1;

        // 返回结果的时候应该直接判断当前子树是否还满足平衡二叉树(左右高度差不大于1)
        // 如果不满足则返回 -1，因为力扣中将树根节点高度定义为1，所以高度需要加一
        return abs(leftHeight - rightHeight) > 1 ? -1:max(leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false:true;
    }
};

迭代法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 迭代过程有点难以理解，而且效率低，了解一下吧
    int getDepth(TreeNode* current) {
        stack<TreeNode*> st;
        if(current) st.push(current);
        int depth = 0, res = 0;

        // 将传入节点作为根节点，求其深度，即为当前节点的高度
        while(!st.empty()) {
            auto node = st.top();
            if(node) {
                st.pop();
                st.push(node);
                // 这里的 NULL 主要是作为回溯标志
                // 表明下次遇到 null 时，前一个节点已经完成左右子树的遍历，需要回退 depth--
                st.push(NULL);

                depth++;

                if(node->right) st.push(node->right);
                if(node->left) st.push(node->left);
            } else {
                // 前一个节点已经完成左右子树的遍历，需要回退 depth--
                // 弹出回退标志
                st.pop();
                // 获取上一个节点
                node = st.top();
                // 弹出节点（其子节点已经完成遍历）
                st.pop();
                depth--;
            }
            res = res > depth ? res:depth;
        }
        return res;
    }
    // 用栈模拟「左右中」后序遍历过程
    bool isBalanced(TreeNode* root) {
        stack<TreeNode*> st;
        if(!root) return true;

        st.push(root);

        while(!st.empty()) {
            auto node = st.top();
            st.pop();
            if(abs(getDepth(node->left) - getDepth(node->right)) > 1) return false;

            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
        }
        return true;
    }
};