104.E 二叉树的最大深度

Problem: 104. 二叉树的最大深度

思路

思路1：深度优先遍历。ans = max(l, r) + 1

思路2：广度优先遍历。层次遍历，每遍历一行，深度加一。

Code

代码1：

func maxDepthV1(root *TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := maxDepthV1(root.Left)
	rightDepth := maxDepthV1(root.Right)
	if leftDepth > rightDepth {
		return leftDepth + 1
	} else {
		return rightDepth + 1
	}
}

代码2：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	ans := 0
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue)
		for size > 0 {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
			size--
		}
		ans++
	}

	return ans
}