美文网首页
剑指offer 55 是否平衡二叉树

剑指offer 55 是否平衡二叉树

作者: 再凌 | 来源:发表于2020-05-05 14:26 被阅读0次

    输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

    看似简单的一道题, 为啥我就做不出来呢???

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    
    int _caculate(struct TreeNode* root){
        if(root==NULL){
            return 0;
        }
        int left=_caculate(root->left);
        int right=_caculate(root->right);
        if(left!=-1&&right!=-1&&abs(left-right)<2){
            if(left>right){
                return left+1;
            }else{
                return right+1;
            }
        }else{
            return -1;
        }
    }
    
    bool isBalanced(struct TreeNode* root){
        int res = _caculate(root);
        if(res == -1){
            return false;
        }else{
            return true;
        }
    }
    
    

    相关文章

      网友评论

          本文标题:剑指offer 55 是否平衡二叉树

          本文链接:https://www.haomeiwen.com/subject/hmemghtx.html