文档章节

二叉树(高度、结点个数)递归

老汉-憨憨
 老汉-憨憨
发布于 2017/03/16 18:11
字数 172
阅读 14
收藏 0

#include <iostream>
using namespace std;

// binary tree node
struct Node
{
    int data;
    Node *left,*right;
    Node(int x)
    {
        data = x;
        left = right = NULL;
    }
};

int height(Node *root)
{
    if (!root)
        return 0;

    int hLeft  = height(root->left);
    int hRight = height(root->right);

    return ((hLeft > hRight) ? (hLeft + 1) : (hRight + 1));
}

int size(Node *root)
{
   if (!root) 
       return 0;

   return (size(root->left) + size(root->right) + 1);
}

// Driver code
int main()
{
    Node *root = new Node(1);
    root->left = new Node(3);
    root->left->left = new Node(2);
    root->left->right = new Node(1);
    root->left->right->left = new Node(1);
    root->right = new Node(-1);
    root->right->left = new Node(4);
    root->right->left->left = new Node(1);
    root->right->left->right = new Node(2);
    root->right->right = new Node(5);
    root->right->right->right = new Node(2);
    
    int h = height(root);
    cout << "height = " << h << endl;

    int s = size(root);
    cout << "size = " << s << endl;
    return 0;
}

 

输出结果:

height = 4
size = 11

 

© 著作权归作者所有

共有 人打赏支持
老汉-憨憨
粉丝 20
博文 322
码字总数 68382
作品 0
深圳
程序员
私信 提问
二叉树简单操作(下)

一、二叉树基本操作  1. 求二叉树的深度。(树的深度:树中所有节点的层次的最大值称为该树的深度)  2. 求二叉树叶子结点的个数。(叶子节点:度为0的结点称为叶结点,叶节点也称为终端节点...

qq_38646470
2018/01/22
0
0
二叉树基本操作(下)

二叉树基本操作  1. 求二叉树的高度  2. 求二叉树叶子结点的个数  3. 求二叉树结点的个数  4. 求二叉树第K层结点的个数  5. 判断一个节点是否在一棵二叉树中  6. 获取一个节点的双亲结...

qq_38646470
2018/01/22
0
0
算法知识梳理(11) - 二叉树相关算法第一部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/19
0
2
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

rabbitmq安装教程

RabbitMQ有Windows与Linux版本的,这里先写Windows版本的安装。 以前安装软件总是在百度上找某某安装教程,结果能按照教程安装好的软件真的不多。想起先前以为大牛说的一句话,去官网按照官网...

em_aaron
今天
6
0
Android 贝塞尔曲线实践——波浪式运动

一、波浪效果如下 贝塞尔曲线自定义波浪效果的案例很多,同样方法也很简单,大多数和本案例一样使用二次贝塞尔曲线实现,同样还有一种是PathMeasure的方式,这里我们后续补充,先来看贝塞尔曲...

IamOkay
今天
3
0
Nmap之防火墙/IDS逃逸

选项 解释 -f 报文分段 --mtu 指定偏移大小 -D IP欺骗 -sI 原地址欺骗 --source-port 源端口欺骗 --data-length 指定发包长度 --randomize-hosts 目标主机随机排序 --spoof-mac Mac地址欺骗 ...

Frost729
今天
2
0
带你搭一个SpringBoot+SpringData JPA的环境

不知道大家对SpringBoot和Spring Data JPA了解多少,如果你已经学过Spring和Hibernate的话,那么SpringBoot和SpringData JPA可以分分钟上手的。 其实我在学完SpringBoot和SpringData JPA了之...

java菜分享
今天
7
0
Chocolatey 在Window搭建一个开发环境

在看了(利用 Chocolatey 快速在 Windows 下搭建一个开发环境)后,准备从零开始 一、准备工作 1、用管理员权限启动:powershell,执行错误请参考(PowerShell因为在此系统中禁止执行脚本的解...

近在咫尺远在天涯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部