LeetCode 之 JavaScript 解答第104題 —— 二叉樹的最大深度

boredream 發(fā)布于2019-08-23 17:07 / 1001人閱讀

摘要：小鹿題目二叉樹的最大深度給定一個二叉樹，找出其最大深度。二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。求二叉樹的深度，必然要用到遞歸來解決。分別遞歸左右子樹。

Time：2019/4/22
Title: Maximum Depth of Binary Tree
Difficulty: Medium
Author:小鹿

題目：Maximum Depth of Binary Tree（二叉樹的最大深度）

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

給定一個二叉樹，找出其最大深度。二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

Solve：

▉ 問題分析

求二叉樹的最大深度，我們要知道樹的深度怎么計算的？

1）樹的深度，深度，顧名思義，從上到下，第一層為 1，每向下一層，深度 + 1。

2）觀察上圖，我們計算時，只需記錄兩個子樹最深的結(jié)點(diǎn)為主。

3）求二叉樹的深度，必然要用到遞歸來解決。

▉ 算法思路

1）判斷樹是否為 null。2）分別遞歸左右子樹。
3）只計算疊加計數(shù)（遞歸最深）最大的數(shù)字。

▉ 代碼實(shí)現(xiàn)

var maxDepth = function(root) {
    // 如果根節(jié)點(diǎn)為 null 
    if(root === null) return 0;
    // 遞歸左子樹
    let depthLeft  = maxDepth(root.left);
    // 遞歸右子樹
    let depthRight  = maxDepth(root.right);
    // 將子問題合并求總問題
    return Math.max(depthLeft,depthRight) + 1;
};

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
歡迎關(guān)注我個人公眾號：「一個不甘平凡的碼農(nóng)」，記錄了自己一路自學(xué)編程的故事。