二叉树的深度

1. 题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

2. 思路

1+左右子树深度的较大者

3. 实现

• java

public class 二叉树的深度
{
    public int TreeDepth(TreeNode root)
    {
        //检查参数是否为空
        if (root == null)
        {
            return 0;
        }
        //1+左右子树深度的较大者
        return 1 + Math.max(this.TreeDepth(root.left), this.TreeDepth(root.right));
    }
}

• go

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param pRoot TreeNode类
 * @return int整型
 */
//时间复杂度：O(n)
//空间复杂度：O(n),当退化到链表时
func TreeDepth(pRoot *TreeNode) int {
	if pRoot == nil {
		return 0
	}

	return 1 + max(TreeDepth(pRoot.Left), TreeDepth(pRoot.Right))
}
func max(a int, b int) int {
	if a < b {
		return b
	}
	return a
}

4. 参考

• 二叉树的深度_牛客网
• Maximum Depth of Binary Tree - LeetCode