CareerCup-4.1

简介:

Implement a function to check if a tree is balanced For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one

答案是两次遍历分别求出最大深度与最小深度,我试着一次遍历求出最大和最小深度

#include <iostream>
using namespace std;
typedef int Data;

struct TreeNode
{
    TreeNode(Data d):data(d){left = right = NULL;};
    Data data;
    TreeNode* left;
    TreeNode* right;
};

class Tree
{
public:
    Tree():root(NULL){};
    TreeNode* root;
    void insert(Data data, TreeNode* node = NULL)
    {
        if(root == NULL)
        {
            root = new TreeNode(data);
            return;
        }
        if(node == NULL) node = root;
        if(data == node->data)
        {
            return;
        } else if(data < node->data) {
            if(node->left == NULL)
                node->left = new TreeNode(data);    
            else
                insert(data, node->left);
        } else {
            if(node->right == NULL)
                node->right = new TreeNode(data);
            else
                insert(data, node->right);
        }
    };
    void inorderPrint(TreeNode* TreeNode)
    {
        if(TreeNode == root)
            cout<<"Print:"<<endl;
        if(TreeNode != NULL)
        {
            inorderPrint(TreeNode->left);
            cout<<TreeNode->data<<" ";
            inorderPrint(TreeNode->right);
        }
        if(TreeNode == root)
            cout<<endl<<"End"<<endl;
    };
    void preorderPrint(TreeNode* TreeNode)
    {
        if(TreeNode == root)
            cout<<"Print:"<<endl;
        if(TreeNode != NULL)
        {
            cout<<TreeNode->data<<" ";
            preorderPrint(TreeNode->left);
            preorderPrint(TreeNode->right);
        }
        if(TreeNode == root)
            cout<<endl<<"End"<<endl;
    };
    void postorderPrint(TreeNode* node)
    {
        if(node == root)
            cout<<"Print:"<<endl;
        if(node != NULL)
        {
            postorderPrint(node->left);
            postorderPrint(node->right);
            cout<<node->data<<" ";
        }
        if(node == root)
            cout<<endl<<"End"<<endl;
    };
    bool isBalanced()
    {
        int min=0 ,max=0;
        calDepth(root, 0, &min, &max);
        cout<<"Min: "<<min<<endl<<"Max: "<<max<<endl;
        if(max - min < 2)
            return true;
        else
            return false;
    };
    void calDepth(TreeNode* node, int depth, int* min, int* max)
    {
        if(node == NULL) return;
        depth++;
        if(node->left == NULL && node->right == NULL)
        {
            if(depth < *min || *min <= 0)
                *min = depth;
            if(depth > *max || *max <= 0)
                *max = depth;
        }
        calDepth(node->left, depth, min, max);
        calDepth(node->right, depth, min, max);
    };
};

int main()
{
    Tree tree;
    tree.insert(5);
    tree.insert(1);
    tree.insert(7);
    tree.insert(4);
    tree.insert(3);
    cout<<boolalpha<<tree.isBalanced();
    system("pause");
};

目录
相关文章
|
前端开发 物联网 程序员
初步认识低代码
低代码不是一个纯粹的编程工具,把它叫做生产力提高工具更为合适。
184 4
|
11月前
|
SQL 存储 OLAP
ClickHouse 在什么场景下才管用?
ClickHouse 是一款以速度快著称的分析型数据库,尤其在列式宽表遍历方面表现出色。然而,面对复杂查询和关联运算时,ClickHouse 的性能急剧下降,甚至无法执行某些任务。相比之下,esProc SPL 通过更简洁的 SPL 语法和强大的优化能力,在各种复杂场景下均表现出色,全面超越 ClickHouse。实际案例显示,esProc SPL 在处理大规模数据时,性能提升可达数十倍。
|
运维 监控 数据可视化
ARMS应用监控
【8月更文挑战第25天】
339 1
|
数据采集 网络安全 UED
揭秘豆瓣网站爬虫:利用lua-resty-request库获取图片链接
本文探讨了如何使用Lua的lua-resty-request库和爬虫代理IP技术从豆瓣网站高效获取图片链接。通过定制请求头部和代理服务,可以应对反爬虫机制,提高爬虫的稳定性和匿名性。示例代码展示了一种方法,但实际应用需考虑版权和法律法规。
233 2
揭秘豆瓣网站爬虫:利用lua-resty-request库获取图片链接
|
存储 算法 数据挖掘
【数据挖掘】2022年京东算法工程师笔试题(23届)
2022年京东面向23届的算法工程师笔试题,包含了关于MySQL内部存储代码的优势、SQL使用、数学问题、ReLU函数特性、栈操作以及F1-Score计算等方面的问题。
305 0
|
JavaScript 前端开发
自定义事件的触发 dispatchEvent 的用法
自定义事件的触发 dispatchEvent 的用法
|
存储 分布式计算 数据可视化
ERP系统中的大数据分析与处理:驱动企业智能决策
【7月更文挑战第29天】 ERP系统中的大数据分析与处理:驱动企业智能决策
894 0
|
算法 Java
3、Drools规则引擎-为什么选择Drools
Drools 是用 Java 语言编写的具有一个易于访问企业策略、易于调整以及易于管理的开源业务规则引擎 ,其基于CHARLES FORGY’S的RETE算法 符合业内标准,速度快且效率高。 业务分析师人员或审核人员可以利用它轻松查看业务规则, 检验已编码的规则执行了所需的业务规则。
532 0
|
SQL 索引
SQL查看表字段信息如:字段名、字段类型、字段精度、字段大小、索引、主键等
表名、字段名、字段类型、字段精度、字段大小 字段名、是否为主键、字段类型、字段大小、索引名
1513 0
SQL查看表字段信息如:字段名、字段类型、字段精度、字段大小、索引、主键等
|
人工智能 运维 Kubernetes
阿里云容器服务 ACK AI 助手正式上线
期待已久!阿里云容器服务 ACK AI 助手正式上线