JZ-C-39

剑指offer第三十九题:二叉树的深度:输入一棵二叉树的根结点,求该树的深度

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
//============================================================================
// Name        : JZ-C-39.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 二叉树的深度:输入一棵二叉树的根结点,求该树的深度
//============================================================================
 
#include <iostream>
#include <stdio.h>
#include "BinaryTree.h"
using namespace std;
/**
 * 这是前序遍历吗?(不是吧,后序遍历,以计算路径和)
 */
int TreeDepth(BinaryTreeNode* pRoot) {
    if (pRoot == NULL)
        return 0;
 
    int nLeft = TreeDepth(pRoot->m_pLeft);
    int nRight = TreeDepth(pRoot->m_pRight);
 
    return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
 
// ====================测试代码====================
void Test(BinaryTreeNode* pRoot, int expected) {
    int result = TreeDepth(pRoot);
    if (expected == result)
        printf("Test passed.\n");
    else
        printf("Test failed.\n");
}
 
//            1
//         /      \
//        2        3
//       /\         \
//      4  5         6
//        /
//       7
void Test1() {
    printf("Test1 begins.\n");
 
    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, NULL, pNode6);
    ConnectTreeNodes(pNode5, pNode7, NULL);
 
    Test(pNode1, 4);
 
    DestroyTree(pNode1);
}
 
//               1
//              /
//             2
//            /
//           3
//          /
//         4
//        /
//       5
void Test2() {
    printf("Test2 begins.\n");
 
    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
 
    ConnectTreeNodes(pNode1, pNode2, NULL);
    ConnectTreeNodes(pNode2, pNode3, NULL);
    ConnectTreeNodes(pNode3, pNode4, NULL);
    ConnectTreeNodes(pNode4, pNode5, NULL);
 
    Test(pNode1, 5);
 
    DestroyTree(pNode1);
}
 
// 1
//  \
//   2
//    \
//     3
//      \
//       4
//        \
//         5
void Test3() {
    printf("Test3 begins.\n");
 
    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
 
    ConnectTreeNodes(pNode1, NULL, pNode2);
    ConnectTreeNodes(pNode2, NULL, pNode3);
    ConnectTreeNodes(pNode3, NULL, pNode4);
    ConnectTreeNodes(pNode4, NULL, pNode5);
 
    Test(pNode1, 5);
 
    DestroyTree(pNode1);
}
 
// 树中只有1个结点
void Test4() {
    printf("Test4 begins.\n");
 
    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    Test(pNode1, 1);
 
    DestroyTree(pNode1);
}
 
// 树中没有结点
void Test5() {
    printf("Test5 begins.\n");
 
    Test(NULL, 0);
}
 
int main(int argc, char** argv) {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
 
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注