110. 平衡二叉树

leetcode 110.平衡二叉树

题目描述

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

该二叉树不是平衡二叉树，不是 每个节点的左右子树高度差不超过1。

递归解法

每次递归结束时都是当二叉树为一个根节点，return 1+0+0；

后序遍历

class Solution {
    int getheight(TreeNode* node)
    {
        if(node ==nullptr) 
            return 0;
        int lheight=  getheight(node->left); //左
        if(lheight==-1) return -1;
        int rheight = getheight(node->right); //右
        if(rheight==-1) return-1;
        return abs(lheight-rheight)>1? -1:  1+max(lheight,rheight); //中 
        //高度差超过1时，返回-1，否则返回当前二叉树的高度

    }

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