// 程序员面试100题(算法)之递归求二叉树深度
#include "stdafx.h"
#include <iostream>
#include <deque>
using namespace std;
struct BiTreeNode
{
BiTreeNode *leftNode;
BiTreeNode *rightNode;
int value;
};
BiTreeNode *CreateBiTree(BiTreeNode *&root)
{
int data = 0;
cin >> data;
if(-1 == data)
return NULL;
else
{
root= (BiTreeNode*)malloc(sizeof(BiTreeNode));
if(root)
{
root->value = data;
root->leftNode = NULL;
root->rightNode = NULL;
CreateBiTree(root->leftNode);
CreateBiTree(root->rightNode);
}
else
{
cout << "No space" <<endl;
return NULL;
}
}
return root;
}
int TreeDepth(BiTreeNode *root)
{
// the depth of a empty tree is 0
if(!root)
return 0;
// the depth of left sub-tree
int nLeft = TreeDepth(root->leftNode);
// the depth of right sub-tree
int nRight = TreeDepth(root->rightNode);
// depth is the binary tree
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
int _tmain(int argc, _TCHAR* argv[])
{
BiTreeNode *root = NULL;
cout << "Please create the tree with preorder(-1 means NULL):" << endl;
CreateBiTree(root);
cout << "Depth of tree is:" << endl;
cout << TreeDepth(root) << endl;
return 0;
}
分享到:
相关推荐
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、...
说起二叉树的遍历,大学里讲的是递归算法,大多数人首先想到也是递归算法。但作为一个有理想有追求的程序员。也应该学学非递归算法实现二叉树遍历。二叉树的非递归算法需要用到辅助栈,算法着实巧妙,令人脑洞大开。...
一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的。现举一个非递归遍历的方法如下,供大家参考。 具体代码如下: class ...
》主要定位于有一定C/C++语言编程基础、想通过学习算法与数据结构提升编程水平的读者,也可作为具有一定编程经验的程序员以及大中专院校学生学习数据结构和算法的参考书。 第1篇 算法基础篇 1 第1章 算法概述 2 ...
《算法导论》是一本好书,但是他太难了,就算是现在的我,再不借助资料的情况下,也绝看不...超四十种常见算法思想:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
该程序员面试指南涉及栈,队列,链表,二叉树,递归和动态规划以及字符串等算法以及常见数据结构的算法题详解,非常适合正在学习算法或者是正在找工作的人群,希望会对你们有所帮助
树 * 字典树 * 遍历-层次遍历 * 遍历-中序遍历-非递归 * 遍历-前序遍历-非递归 * 遍历-后序遍历-非递归 ...* 二叉树-的最大深度 数组&字符串 查找排序 排列组合 动态规划 树 链表 数学 位运算 编程之美
5.7 递归二叉树算法 5.8 图的遍历 5.9 综述 第三部分 排序 第6章 基本排序方法 6.1 游戏规则 6.2 选择排序 6.3 插入排序 6.4 冒泡排序 6.5 基本排序方法的性能特征 6.6 希尔排序 ...
程序员笔试知识点总结整理。包括:常考基础必知必会;二叉树三种遍历的非递归算法;线性表;树与二叉树;图;单源最短路径;等。
全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、二叉树、红黑树、哈希表及图形等知识。附录中则提供了运行专题Applet和例程、相关书籍和问题解答。本书提供了学完一门编程...
c语言常见算法,适合即将参加软考(二叉树中序输出,全排列递归,快速排序算法,二路归并程序算法等)
对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么...
leetcode中国 记录在大学期间学习的一些数据结构与算法的代码实现 数据结构 数组 链表 二叉树 栈队列 算法 排序 递归 贪心算法 动态规划 剑指Offer练习题
面试考算法,通过率极低 看过c、c++、java版算法,javascript不会写 怎么学算法 通过“解题”夯实基础算法 理解算法的本质学会挖掘“规律” 举一反三学会变通和延伸 基础算法 字符串 反转字符串中的单词 计算二进制...
对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示...
对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为...
已知二叉树的后序遍历和中序遍历序列,构造对应的二叉树,并非递归前序遍历该二叉树。 三、综合题 9. 线性表综合题 (1) 按照输入的顺序建立顺序表 (2) 对顺序表进行排序(直接插入、冒泡、选择、快速、合并)...
对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为...
实现一种算法来验证二叉树是否已排序。 看 我有一个链表,可能有一个循环。 如何判断是否存在循环? 复杂度如何? 见 - O(1) 时间,O(n) 空间 我有两个不适合任何 Java 数字类型的大数(即,忽略 BigDecimal 和 ...
的表示程序员面试金典上面的题目 :party_popper:该仓库所有题目代码见: 附:已做题目目录(截至 2020.04.15) 题目序号 题目链接 题目难度 提交时间 关键点 值得一读 1 简单 8 个月前 2 中等 2 个月前 3 中等 7 个...