欣迪

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -100 <= Node.val <= 100

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    let deepth = 0
    const digg = (node, layer = 0) => {
        if (node) {
            layer++
            if (node.left, layer) {
                digg(node.left, layer)
            }
            if (node.right) {
                digg(node.right, layer)
            }
        }
        
        return deepth = Math.max(deepth, layer)
    }
   
    return digg(root)
};

先附上我第一次的解法。

毫無疑問,這題必須使用遞迴方法往下不斷探索左邊分支和右邊分支的深度,最後挖得最深的就是結果。

但我第一次的想法仍然稍顯累贅,而且在裡面定義的變數,會造成記憶體用量的爆增。參考了討論區後修改如下:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

var maxDepth = function(root) {
    if (!root) return 0
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

修改後精簡很多,主要的概念是將 maxDepth 直接當作遞迴用的 function。

用上圖說明。我們帶入第一個最放面的 root,隨著遞迴向下,會一路奔向最底層的 node。

接下來就是從左右比較,不斷將深度往上加。 最後得到我們要的解答 3。

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。