110. 平衡二叉树


?做题思路or感想:

  • 用递归后序遍历二叉树,然后从底部开始记录高度为0,然后往上加1。

  • 每一次操作节点的时候比较左右子树的高度,如果有一棵树不符合条件,则直接把-1返回到最顶的根节点

  • class Solution {
    public:
        int getDepth(TreeNode* cur) {
            if (cur == nullptr)return 0;	//节点触底后,从高度为0开始计数
            //检验左右子树是否符合条件
            int leftDepth = getDepth(cur->left);
            if (leftDepth == -1) return -1;
            int rightDepth = getDepth(cur->right);
            if (rightDepth == -1)return -1;
            if (abs(leftDepth - rightDepth) > 1)return -1;
            else {
                //若符合条件,则往上+1
                return max(leftDepth, rightDepth) + 1;
            }
        }
        bool isBalanced(TreeNode* root) {
            if (getDepth(root) != -1)return true;
            else return false;
        }
    };