二叉樹的深度，二叉樹深度

二叉樹的深度，二叉樹深度

題目：輸入一棵二叉樹的根節點，求該樹的深度。從根節點到葉子結點一次經過的結點形成樹的一條路徑，最長路徑的長度為樹的深度。根節點的深度為1。

思路:如果根節點為空，則深度為0，返回0，遞歸的出口，如果根節點不為空，那麼深度至少為1，然後我們求他們左右子樹的深度，比較左右子樹深度值，返回較大的那一個，通過遞歸調用

  1 #include<stdio.h>
  2 #include "stdafx.h"
  3 
  4 struct BinaryTreeNode
  5 {
  6     int              m_nValue;
  7     BinaryTreeNode*  m_pLeft;
  8     BinaryTreeNode*  m_pRight;
  9 };
 10 
 11 BinaryTreeNode* CreateBinaryTreeNode(int value)
 12 {
 13     BinaryTreeNode* pNode = new BinaryTreeNode();
 14     pNode->m_nValue = value;
 15     pNode->m_pLeft = NULL;
 16     pNode->m_pRight = NULL;
 17 }
 18 
 19 void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
 20 {
 21     if(pParent != NULL)
 22     {
 23         pParent->m_pLeft = pLeft;
 24         pParent->m_pRight = pRight;
 25     }
 26 }
 27 
 28 void PrintTreeNode(BinaryTreeNode* pNode)
 29 {
 30     if(pNode != NULL)
 31     {
 32         printf("value of this node is: %d\n", pNode->m_nValue);
 33         
 34         if(pNode->m_pLeft != NULL)
 35             printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);
 36         else
 37             printf("left child is null.\n");
 38         
 39         if(pNode->m_pRight != NULL)
 40             printf("value of its right child is: %d.\n",pNode->m_pRight->m_nValue);
 41         else
 42             printf("right child is null.\n");
 43     }
 44     else
 45     {
 46         printf("this node is null.\n");
 47     }
 48     printf("\n");
 49 }
 50 
 51 void PrintTree(BinaryTreeNode* pRoot)
 52 {
 53     PrintTreeNode(pRoot);
 54     
 55     if(pRoot != NULL)
 56     {
 57         if(pRoot->m_pLeft != NULL)
 58             PrintTree(pRoot->m_pLeft);
 59         
 60         if(pRoot->m_pRight != NULL) 
 61             PrintTree(pRoot->m_pRight);
 62     }
 63 }
 64 
 65 void DestroyTree(BinaryTreeNode* pRoot)
 66 {
 67     if(pRoot != NULL)
 68     {
 69         BinaryTreeNode* pLeft = pRoot->m_pLeft;
 70         BinaryTreeNode* pRight = pRoot->m_pRight;
 71         
 72         delete pRoot;
 73         pRoot = NULL;
 74         
 75         DestroyTree(pLeft);
 76         DestroyTree(pRight);
 77     }
 78 }
 79 
 80 int TreeDepth(BinaryTreeNode* pRoot)
 81 {
 82     if(pRoot == NULL)
 83         return 0;
 84     
 85     int nLeft = TreeDepth(pRoot->m_pLeft);
 86     int nRight = TreeDepth(pRoot->m_pRight);
 87     
 88     return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
 89 }
 90 
 91 //            1
 92 //         /      \
 93 //        2        3
 94 //       /\         \
 95 //      4  5         6
 96 //        /
 97 //       7
 98 
 99 int main()
100 {
101     BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
102     BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
103     BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
104     BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
105     BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
106     BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
107     BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
108     
109     ConnectTreeNodes(pNode1, pNode2, pNode3);
110     ConnectTreeNodes(pNode2, pNode4, pNode5);
111     ConnectTreeNodes(pNode3, NULL,   pNode6);
112     ConnectTreeNodes(pNode5, pNode7, NULL  );
113     
114     int result = TreeDepth(pNode1);
115     printf("The depth of binarytree is %d\n", result);
116     
117     DestroyTree(pNode1);
118     return 0;
119 }