Skip to content

Commit bbc8255

Browse files
zhedahhtzhedahht
committed
Initial commit for question 55(1)
1 parent c23f6a9 commit bbc8255

4 files changed

Lines changed: 329 additions & 0 deletions

File tree

‎55_01_TreeDepth/55_01_TreeDepth.vcxproj‎

Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
<?xml version="1.0" encoding="utf-8"?>
2+
<Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3+
<ItemGroup Label="ProjectConfigurations">
4+
<ProjectConfiguration Include="Debug|Win32">
5+
<Configuration>Debug</Configuration>
6+
<Platform>Win32</Platform>
7+
</ProjectConfiguration>
8+
<ProjectConfiguration Include="Release|Win32">
9+
<Configuration>Release</Configuration>
10+
<Platform>Win32</Platform>
11+
</ProjectConfiguration>
12+
<ProjectConfiguration Include="Debug|x64">
13+
<Configuration>Debug</Configuration>
14+
<Platform>x64</Platform>
15+
</ProjectConfiguration>
16+
<ProjectConfiguration Include="Release|x64">
17+
<Configuration>Release</Configuration>
18+
<Platform>x64</Platform>
19+
</ProjectConfiguration>
20+
</ItemGroup>
21+
<PropertyGroup Label="Globals">
22+
<ProjectGuid>{B920F64B-2428-4BC8-BF59-052717ACADCC}</ProjectGuid>
23+
<Keyword>Win32Proj</Keyword>
24+
<RootNamespace>My55_01_TreeDepth</RootNamespace>
25+
<WindowsTargetPlatformVersion>8.1</WindowsTargetPlatformVersion>
26+
</PropertyGroup>
27+
<Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" />
28+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'" Label="Configuration">
29+
<ConfigurationType>Application</ConfigurationType>
30+
<UseDebugLibraries>true</UseDebugLibraries>
31+
<PlatformToolset>v140</PlatformToolset>
32+
<CharacterSet>Unicode</CharacterSet>
33+
</PropertyGroup>
34+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'" Label="Configuration">
35+
<ConfigurationType>Application</ConfigurationType>
36+
<UseDebugLibraries>false</UseDebugLibraries>
37+
<PlatformToolset>v140</PlatformToolset>
38+
<WholeProgramOptimization>true</WholeProgramOptimization>
39+
<CharacterSet>Unicode</CharacterSet>
40+
</PropertyGroup>
41+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'" Label="Configuration">
42+
<ConfigurationType>Application</ConfigurationType>
43+
<UseDebugLibraries>true</UseDebugLibraries>
44+
<PlatformToolset>v140</PlatformToolset>
45+
<CharacterSet>Unicode</CharacterSet>
46+
</PropertyGroup>
47+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'" Label="Configuration">
48+
<ConfigurationType>Application</ConfigurationType>
49+
<UseDebugLibraries>false</UseDebugLibraries>
50+
<PlatformToolset>v140</PlatformToolset>
51+
<WholeProgramOptimization>true</WholeProgramOptimization>
52+
<CharacterSet>Unicode</CharacterSet>
53+
</PropertyGroup>
54+
<Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
55+
<ImportGroup Label="ExtensionSettings">
56+
</ImportGroup>
57+
<ImportGroup Label="Shared">
58+
</ImportGroup>
59+
<ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
60+
<Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
61+
</ImportGroup>
62+
<ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
63+
<Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
64+
</ImportGroup>
65+
<ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
66+
<Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
67+
</ImportGroup>
68+
<ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
69+
<Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
70+
</ImportGroup>
71+
<PropertyGroup Label="UserMacros" />
72+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
73+
<LinkIncremental>true</LinkIncremental>
74+
</PropertyGroup>
75+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
76+
<LinkIncremental>true</LinkIncremental>
77+
</PropertyGroup>
78+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
79+
<LinkIncremental>false</LinkIncremental>
80+
</PropertyGroup>
81+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
82+
<LinkIncremental>false</LinkIncremental>
83+
</PropertyGroup>
84+
<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
85+
<ClCompile>
86+
<PrecompiledHeader>
87+
</PrecompiledHeader>
88+
<WarningLevel>Level3</WarningLevel>
89+
<Optimization>Disabled</Optimization>
90+
<PreprocessorDefinitions>WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
91+
</ClCompile>
92+
<Link>
93+
<SubSystem>Console</SubSystem>
94+
<GenerateDebugInformation>true</GenerateDebugInformation>
95+
</Link>
96+
</ItemDefinitionGroup>
97+
<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
98+
<ClCompile>
99+
<PrecompiledHeader>
100+
</PrecompiledHeader>
101+
<WarningLevel>Level3</WarningLevel>
102+
<Optimization>Disabled</Optimization>
103+
<PreprocessorDefinitions>_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
104+
</ClCompile>
105+
<Link>
106+
<SubSystem>Console</SubSystem>
107+
<GenerateDebugInformation>true</GenerateDebugInformation>
108+
</Link>
109+
</ItemDefinitionGroup>
110+
<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
111+
<ClCompile>
112+
<WarningLevel>Level3</WarningLevel>
113+
<PrecompiledHeader>
114+
</PrecompiledHeader>
115+
<Optimization>MaxSpeed</Optimization>
116+
<FunctionLevelLinking>true</FunctionLevelLinking>
117+
<IntrinsicFunctions>true</IntrinsicFunctions>
118+
<PreprocessorDefinitions>WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
119+
</ClCompile>
120+
<Link>
121+
<SubSystem>Console</SubSystem>
122+
<EnableCOMDATFolding>true</EnableCOMDATFolding>
123+
<OptimizeReferences>true</OptimizeReferences>
124+
<GenerateDebugInformation>true</GenerateDebugInformation>
125+
</Link>
126+
</ItemDefinitionGroup>
127+
<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
128+
<ClCompile>
129+
<WarningLevel>Level3</WarningLevel>
130+
<PrecompiledHeader>
131+
</PrecompiledHeader>
132+
<Optimization>MaxSpeed</Optimization>
133+
<FunctionLevelLinking>true</FunctionLevelLinking>
134+
<IntrinsicFunctions>true</IntrinsicFunctions>
135+
<PreprocessorDefinitions>NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
136+
</ClCompile>
137+
<Link>
138+
<SubSystem>Console</SubSystem>
139+
<EnableCOMDATFolding>true</EnableCOMDATFolding>
140+
<OptimizeReferences>true</OptimizeReferences>
141+
<GenerateDebugInformation>true</GenerateDebugInformation>
142+
</Link>
143+
</ItemDefinitionGroup>
144+
<ItemGroup>
145+
<ClCompile Include="TreeDepth.cpp" />
146+
</ItemGroup>
147+
<ItemGroup>
148+
<ProjectReference Include="..\Utilities\Utilities.vcxproj">
149+
<Project>{732da13a-f8bb-4cef-b96d-61de60bdb6a7}</Project>
150+
</ProjectReference>
151+
</ItemGroup>
152+
<Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
153+
<ImportGroup Label="ExtensionTargets">
154+
</ImportGroup>
155+
</Project>

‎55_01_TreeDepth/55_01_TreeDepth.vcxproj.filters‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
<?xml version="1.0" encoding="utf-8"?>
2+
<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3+
<ItemGroup>
4+
<Filter Include="Source Files">
5+
<UniqueIdentifier>{4FC737F1-C7A5-4376-A066-2A32D752A2FF}</UniqueIdentifier>
6+
<Extensions>cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx</Extensions>
7+
</Filter>
8+
<Filter Include="Header Files">
9+
<UniqueIdentifier>{93995380-89BD-4b04-88EB-625FBE52EBFB}</UniqueIdentifier>
10+
<Extensions>h;hh;hpp;hxx;hm;inl;inc;xsd</Extensions>
11+
</Filter>
12+
<Filter Include="Resource Files">
13+
<UniqueIdentifier>{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}</UniqueIdentifier>
14+
<Extensions>rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms</Extensions>
15+
</Filter>
16+
</ItemGroup>
17+
<ItemGroup>
18+
<ClCompile Include="TreeDepth.cpp">
19+
<Filter>Source Files</Filter>
20+
</ClCompile>
21+
</ItemGroup>
22+
</Project>

‎55_01_TreeDepth/TreeDepth.cpp‎

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

‎CodingInterviewChinese2.sln‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -130,6 +130,8 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "53_03_IntegerIdenticalToInd
130130
EndProject
131131
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "54_KthNodeInBST", "54_KthNodeInBST\54_KthNodeInBST.vcxproj", "{050F6A72-5004-42F6-8E1A-BA825C6C845B}"
132132
EndProject
133+
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "55_01_TreeDepth", "55_01_TreeDepth\55_01_TreeDepth.vcxproj", "{B920F64B-2428-4BC8-BF59-052717ACADCC}"
134+
EndProject
133135
Global
134136
GlobalSection(SolutionConfigurationPlatforms) = preSolution
135137
Debug|Any CPU = Debug|Any CPU
@@ -762,6 +764,16 @@ Global
762764
{050F6A72-5004-42F6-8E1A-BA825C6C845B}.Release|x64.Build.0 = Release|x64
763765
{050F6A72-5004-42F6-8E1A-BA825C6C845B}.Release|x86.ActiveCfg = Release|Win32
764766
{050F6A72-5004-42F6-8E1A-BA825C6C845B}.Release|x86.Build.0 = Release|Win32
767+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Debug|Any CPU.ActiveCfg = Debug|Win32
768+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Debug|x64.ActiveCfg = Debug|x64
769+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Debug|x64.Build.0 = Debug|x64
770+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Debug|x86.ActiveCfg = Debug|Win32
771+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Debug|x86.Build.0 = Debug|Win32
772+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Release|Any CPU.ActiveCfg = Release|Win32
773+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Release|x64.ActiveCfg = Release|x64
774+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Release|x64.Build.0 = Release|x64
775+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Release|x86.ActiveCfg = Release|Win32
776+
{B920F64B-2428-4BC8-BF59-052717ACADCC}.Release|x86.Build.0 = Release|Win32
765777
EndGlobalSection
766778
GlobalSection(SolutionProperties) = preSolution
767779
HideSolutionNode = FALSE

0 commit comments

Comments
 (0)