面试题：二叉树的深度

题目：输入一棵二叉树的根节点，求该树的深度。从根节点到叶子结点一次经过的结点形成树的一条路径，最长路径的长度为树的深度。根节点的深度为1。

解体思路：

如果根节点为空，则深度为0，返回0，递归的出口
如果根节点不为空，那么深度至少为1，然后我们求他们左右子树的深度，
比较左右子树深度值，返回较大的那一个
通过递归调用

代码实现

View Code

#include<iostream>
#include<stdlib.h>
using namespace std;

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;
    return pNode;
}

//连接二叉树结点
void ConnectTreeNodes(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight)
{
    if(pParent!=NULL)
    {
        pParent->m_pLeft=pLeft;
        pParent->m_pRight=pRight;
    }
}

//求二叉树深度
int TreeDepth(BinaryTreeNode* pRoot)//计算二叉树深度
{
    if(pRoot==NULL)//如果pRoot为NULL，则深度为0，这也是递归的返回条件
        return 0;
    //如果pRoot不为NULL，那么深度至少为1，所以left和right=1
    int left=1;
    int right=1;
    left+=TreeDepth(pRoot->m_pLeft);//求出左子树的深度
    right+=TreeDepth(pRoot->m_pRight);//求出右子树深度

    return left>right?left:right;//返回深度较大的那一个
}

void main()
{
//            1
//         /      \
//        2        3
//       /\         \
//      4  5         6
//           /
//        7
    //创建树结点
    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 depth=TreeDepth(pNode1);
    cout<<depth<<endl;

    system("pause");
}

秒客网

面试题：二叉树的深度

相关文章