-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path55_01_TreeDepth.cpp
More file actions
149 lines (123 loc) · 3.59 KB
/
55_01_TreeDepth.cpp
File metadata and controls
149 lines (123 loc) · 3.59 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*******************************************************************
Copyright(c) 2016, Harry He
All rights reserved.
Distributed under the BSD license.
(See accompanying file LICENSE.txt at
https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
*******************************************************************/
//==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者：何海涛
//==================================================================
// 面试题55（一）：二叉树的深度
// 题目：输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的
// 结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
#include <cstdio>
#include "./Utilities/BinaryTree.h"
int TreeDepth(const BinaryTreeNode* pRoot)
{
if(pRoot == nullptr)
return 0;
int nLeft = TreeDepth(pRoot->m_pLeft);
int nRight = TreeDepth(pRoot->m_pRight);
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
// ====================测试代码====================
void Test(const char* testName, const BinaryTreeNode* pRoot, int expected)
{
int result = TreeDepth(pRoot);
if(expected == result)
printf("%s passed.\n", testName);
else
printf("%s FAILED.\n", testName);
}
// 1
// / \
// 2 3
// /\ \
// 4 5 6
// /
// 7
void Test1()
{
BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
ConnectTreeNodes(pNode1, pNode2, pNode3);
ConnectTreeNodes(pNode2, pNode4, pNode5);
ConnectTreeNodes(pNode3, nullptr, pNode6);
ConnectTreeNodes(pNode5, pNode7, nullptr);
Test("Test1", pNode1, 4);
DestroyTree(pNode1);
}
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
void Test2()
{
BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
ConnectTreeNodes(pNode1, pNode2, nullptr);
ConnectTreeNodes(pNode2, pNode3, nullptr);
ConnectTreeNodes(pNode3, pNode4, nullptr);
ConnectTreeNodes(pNode4, pNode5, nullptr);
Test("Test2", pNode1, 5);
DestroyTree(pNode1);
}
// 1
// \
// 2
// \
// 3
// \
// 4
// \
// 5
void Test3()
{
BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
ConnectTreeNodes(pNode1, nullptr, pNode2);
ConnectTreeNodes(pNode2, nullptr, pNode3);
ConnectTreeNodes(pNode3, nullptr, pNode4);
ConnectTreeNodes(pNode4, nullptr, pNode5);
Test("Test3", pNode1, 5);
DestroyTree(pNode1);
}
// 树中只有1个结点
void Test4()
{
BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
Test("Test4", pNode1, 1);
DestroyTree(pNode1);
}
// 树中没有结点
void Test5()
{
Test("Test5", nullptr, 0);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
return 0;
}