【数据结构与算法】leetcode110.判断平衡二叉树

链接：
题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

---

解题：
求高度：左右中，后序遍历
求深度：中左右，前序遍历
本题利用递归来做，不用迭代法。因为迭代会有重复的寻找过程，不是所有递归都适合迭代。

class Solution {
public:
    int getDepth(TreeNode* root){
        if(root==nullptr)return 0;
        int depthLeft=getDepth(root->left);
        if(depthLeft==-1)return -1;
        int depthRight=getDepth(root->right);
        if(depthRight==-1)return -1;
        return abs(depthLeft-depthRight)>1?-1:1+max(depthRight,depthLeft);
    }

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16