美文网首页面试算法
牛客-剑指0ffer-平衡二叉树

牛客-剑指0ffer-平衡二叉树

作者: wenyilab | 来源:发表于2019-08-08 08:42 被阅读2次

题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == NULL) return true;
        
        int left = TreeDepth(pRoot->left);
        int right = TreeDepth(pRoot->right);
        int diff = left - right;
        
        if (diff > 1 || diff < -1){
            return false;
        }
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);

    }
    int TreeDepth(TreeNode* pRoot){
        if (pRoot == NULL) return 0;
        int left = TreeDepth(pRoot->left);
        int right = TreeDepth(pRoot->right);
        
        return (left>right)?(left+1):(right+1);
    }
};

相关文章

  • 牛客-剑指0ffer-平衡二叉树

    题目描述输入一棵二叉树,判断该二叉树是否是平衡二叉树。

  • 牛客-剑指0ffer-丑数

    题目描述把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含...

  • 牛客-剑指0ffer-反转链表

    题目描述输入一个链表,反转链表后,输出新链表的表头。

  • 牛客-剑指0ffer-矩形覆盖

    题目描述我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,...

  • 牛客-剑指0ffer-跳台阶

    题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不...

  • 牛客-剑指0ffer-替换空格

    题目描述请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过...

  • 牛客-剑指0ffer-重建二叉树

    题目描述输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的...

  • 牛客-剑指0ffer-二叉树的镜像

    题目描述操作给定的二叉树,将其变换为源二叉树的镜像。输入描述: 二叉树的镜像定义:源二叉树 代码

  • 牛客-剑指0ffer-二叉树的深度

    题目描述输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长...

  • 牛客-剑指0ffer-变态跳台阶

    题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳...

网友评论

    本文标题:牛客-剑指0ffer-平衡二叉树

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