示例：
設計算法求給定二叉樹的最大告訴胚鸯，如下圖二叉樹返回的最大高度是3
最容易想到的是可以類似樹的層序遍歷亚铁，我們可以使用廣度優(yōu)先算法遍歷樹的每一層，level遞增搓萧，直到最后一層戚啥。
廣度優(yōu)先搜索：為從起點開始由近及遠進行廣泛的搜索奋单。
// BFS
function maxDepth(root: TreeNode | null): number {
let level = 0
let stack = []
stack.push(root)
while (stack.length) {
let size = stack.length
for (let i = 1; i <= size; i++) {
if (i === 1) level += 1
const node = stack.shift()
if (node.left) stack.push(node.left)
if (node.right) stack.push(node.right)
}
}
return level
};
這個比較容易想到?jīng)]什么難度，但還有一種解法是利用遞歸：
說下怎么想到遞歸的：將問題拆分成一個個子問題虑鼎，樹的最大深度辱匿，就是左右子樹的深度的最大值加1，而樹的末端節(jié)點也剛好符合這個規(guī)律炫彩，因為末端節(jié)點左右子樹深度都為0，max(0, 0) + 1 = 1絮短，所以求二叉樹最大高度可以看作子問題的重復江兢，可以用遞歸。代碼如下：
// 遞歸
function maxDepth(root: TreeNode | null): number {
if (root == null) {
return 0;
} else {
let leftHeight = maxDepth(root.left);
let rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
