[数据结构与算法]【LeetCode-110 | 平衡二叉树】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


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) {}
};



/*
    递归法：利用后序遍历(左右根)求二叉树的高度
    PS:利用前序遍历(根左右)求二叉树的深度
*/

class Solution {
public:
    // 1.确定递归函数的入参及返回值
    int getDepth(TreeNode* node) {
        // 2.确定递归终止的条件
        if(node == nullptr) return 0;
        // 3.确定单层递归逻辑
        int leftDepth = getDepth(node->left);  // 左
        if(leftDepth == -1) return -1;  // 如果左子树已经不是平衡二叉树，则直接返回-1
        
        int rightDepth = getDepth(node->right);  // 右
        if(rightDepth == -1) return -1;  // 如果右子树已经不是平衡二叉树，则直接返回-1

        return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);  // 根
    }

    bool isBalanced(TreeNode* root) {
        return getDepth(root) == -1 ? false : true;
    }
};