/*class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param root TreeNode类
* @return int整型
*/
/**
* 解法一:递归(推荐)
* 时间复杂度:O(n)
* 空间复杂度:O(n)
*/
export function maxDepth(root: TreeNode): number {
if (root == null) return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
/**
* 解法二:递归(拓展)
* 时间复杂度:O(n)
* 空间复杂度:O(n)
*/
// export function maxDepth(root: TreeNode): number {
// if (root == null) return 0
// const queue: TreeNode[] = []
// queue.unshift(root)
// let res = 0
// while (queue.length) {
// const len = queue.length
// for (let i = 0; i < len; i++) {
// const curNode: TreeNode = queue.pop()
// if (curNode.left != null) queue.unshift(curNode.left)
// if (curNode.right != null) queue.unshift(curNode.right)
// }
// res++
// }
// return res
// }