再谈二叉树的深度

题目：输入一棵二叉树的根节点，求该树的深度。从根节点到叶子结点一次经过的结点形成树的一条路径，最长路径的长度为树的深度。根节点的深度为1。前文：二叉树的深度 http://www.linuxidc.com/Linux/2014-09/106591.htm思路:如果根节点为空，则深度为0，返回0，递归的出口，如果根节点不为空，那么深度至少为1，然后我们求他们左右子树的深度，比较左右子树深度值，返回较大的那一个，通过递归调用#include<stdio.h>
#include "stdafx.h"struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};BinaryTreeNode* CreateBinaryTreeNode（int value）
{
BinaryTreeNode* pNode = new BinaryTreeNode（）;
pNode->m_nValue = value;
pNode->m_pLeft = NULL;
pNode->m_pRight = NULL;
}void ConnectTreeNodes（BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight）
{
if（pParent ！= NULL）
{
pParent->m_pLeft = pLeft;
pParent->m_pRight = pRight;
}
}void PrintTreeNode（BinaryTreeNode* pNode）
{
if（pNode ！= NULL）
{
printf（"value of this node is: %d ", pNode->m_nValue）;

if（pNode->m_pLeft ！= NULL）
printf（"value of its left child is: %d. ", pNode->m_pLeft->m_nValue）;
else
printf（"left child is null. "）;

if（pNode->m_pRight ！= NULL）
printf（"value of its right child is: %d. ",pNode->m_pRight->m_nValue）;
else
printf（"right child is null. "）;
}
else
{
printf（"this node is null. "）;
}
printf（" "）;
}void PrintTree（BinaryTreeNode* pRoot）
{
PrintTreeNode（pRoot）;

if（pRoot ！= NULL）
{
if（pRoot->m_pLeft ！= NULL）
PrintTree（pRoot->m_pLeft）;

if（pRoot->m_pRight ！= NULL）
PrintTree（pRoot->m_pRight）;
}
}void DestroyTree（BinaryTreeNode* pRoot）
{
if（pRoot ！= NULL）
{
BinaryTreeNode* pLeft = pRoot->m_pLeft;
BinaryTreeNode* pRight = pRoot->m_pRight;

delete pRoot;
pRoot = NULL;

DestroyTree（pLeft）;
DestroyTree（pRight）;
}
}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）;
}// 1
// /
// 2 3
// /
// 4 5 6
// /
// 7int main（）
{
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 ）;

int result = TreeDepth（pNode1）;
printf（"The depth of binarytree is %d ", result）;

DestroyTree（pNode1）;
return 0;
}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-07/132841.htm