专栏首页AI那点小事剑指offer——平衡二叉树

剑指offer——平衡二叉树

概要

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


思路

如果树为空,返回true。否则递归判断每个树节点的其左右子树高度之差的绝对值是否为0或者1,若是返回true,不是返回false。 注明:这里平衡二叉树不需要是二叉排序树,国内教材为了讲述方便,默认平衡二叉树前提为二叉排序树。


C++ AC代码

#include <iostream>
#include <cmath> 
using namespace std;

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Solution {
    public:
        bool IsBalanced_Solution(TreeNode* pRoot) {
            if(pRoot == NULL){
                return true;
            }
            return this->check_Height(pRoot);
        }

        bool check_Height(TreeNode* pRoot){
            if(pRoot == NULL){
                return true;
            }
            int left = this->TreeDepth(pRoot->left);
            int right = this->TreeDepth(pRoot->right);
            bool flag;
            if(abs(left-right) <= 1){
                return this->IsBalanced_Solution(pRoot->left) && this->IsBalanced_Solution(pRoot->right); 
            }else{
                return false;
            }
        }

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer--二叉树的镜像

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

    AI那点小事
  • 剑指offer——二叉树的深度

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

    AI那点小事
  • 哈夫曼树

    AI那点小事
  • 剑指offer--二叉树的镜像

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

    AI那点小事
  • 剑指offer——二叉树的深度

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

    AI那点小事
  • Leetcode 110. Balanced Binary Tree

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • UPS供应链金融这样做

    UPS是全球著名的第三方物流服务企业。主要业务分为国内快递、国际快递、供应链和货运三类。通过收购美国第一银行成立UPS capital来为企业提供金融支持。

    物流IT圈
  • 乳腺癌单细胞水平的病理特征研究

    而“2019年度技术”(Method of the Year 2019)选择了单细胞多组学,可以对单个细胞的基因组、转录组、蛋白质组、代谢组等生物学标志进行多维...

    生信技能树jimmy
  • 单细胞转录组数据处理综述

    很久以前无意中翻译过一篇单细胞的新闻,单细胞测序 也关注过这方面进展,北大谢晓亮组又更新了他们的单细胞全基因组扩展方法 正好我们博士阶段有一门课是写一个综述...

    生信技能树
  • Django实战-信息资讯-轮播图管理

    Django网络应用开发的5项基础核心技术包括模型(Model)的设计,URL 的设计与配置,View(视图)的编写,Template(模板)的设计和Form(...

    小团子

扫码关注云+社区

领取腾讯云代金券