博客

树的深度求解

---

 

　递归方法求深度   

 　　　　　　　　　寻找递归的条件：

　　　 解题思路： （1）如果树只有一个结点，则树的深度为1。

　　　　　　　      （2）如果根结点只有左子树或者只有右子树，那么这棵树的深度是其根结点的左子树的深度再加1。

　　　　　　　　  （3）如果根结点既有左子树又有右子树，那么这棵树的深度是左子树深度与右子树深度的最大值再加1。

　　　　　　　　

  int GetTreeDepth(BiTree &T)
    {
        if (!T)
        {
            return 0;
        }

        int left = GetTreeDepth(BiTree T->lchild);
        int right =GetTreeDepth(BiTree T->rchild);

        return (left >=right ? left  : right) + 1;
    }