二叉树的深度怎么算?求二叉树深度的算法(思路和代码实现)

KLQ 2020-04-15 16:23:35 java常见问答 3997

你知道求二叉树深度的算法应该如何实现吗?下面要给大家分享3种代码实现和思路,一起来了解一下。

题目:

输入一棵二叉树,求该二叉树的深度。

从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

思路1

代码实现:

class Solution
{
    public:
        int TreeDepth(TreeNode * pRoot)
        {
            if (!pRoot) return 0;
            return max(1 + TreeDepth(pRoot - > left), 1 + TreeDepth(pRoot - > right));
        }
};

思路2

代码实现:

public class Solution
{
    public int TreeDepth(TreeNode pRoot)
    {
        return pRoot == null ? 0 : Math.max(TreeDepth(pRoot.left), TreeDepth(pRoot.right)) + 1;
    }
}

思路3:

递归分析:

从跟节点出发,查询左子树的深度,获取右子树的深度,比较一下,取大的,再加一。

就是整个二叉树的深度

递归的3个条件:

1、边界条件:当前节点下,是否还有子节点,没有返回,有继续递归

2、递归前进段:当前节点下,还有子节点

3、递归返回段:当前节点下,没有子节点

二叉树的深度怎么算

代码实现:

public int TreeDepth1(TreeNode pRoot)
{
    if (pRoot == null)
    {
        return 0;
    }
    int left = TreeDepth1(pRoot.getLeft());
    int right = TreeDepth1(pRoot.getRight());
    return Math.max(left, right) + 1;
}

以上就是关于二叉树深度的相关代码实现和思路整理,更多Java实例,可以继续来本站了解。