Depth of a Binary Tree

1. Problem Description

Given a binary tree, find its depth. A path is formed by the nodes traversed from the root to a leaf, including both the root and the leaf. The length of the longest path is the depth of the tree.

2. Approach

1 + the greater depth of the left and right subtrees

3. Implementation

• java

public class 二叉树的深度
{
    public int TreeDepth(TreeNode root)
    {
        // Check whether the parameter is empty
        if (root == null)
        {
            return 0;
        }
        // 1 + the greater depth of the left and right subtrees
        return 1 + Math.max(this.TreeDepth(root.left), this.TreeDepth(root.right));
    }
}

• go

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

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @param pRoot TreeNode class
 * @return int
 */
// Time complexity: O(n)
// Space complexity: O(n), when the tree degenerates into a linked list
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. References

• Depth of a Binary Tree - NowCoder
• Maximum Depth of Binary Tree - LeetCode