104. Maximum Depth of Binary Tree

讓我們從正式進入 Binary Tree 的世界。在 Binary Tree 的世界中,Linked node 的概念很重要。一個node可以當作一個物件,其中包含val的值、left銜接另一個node、right連接另一個node。

接著我們來看題目

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

假設給你一個 binary tree ,你要給他回傳這個樹的最大深度。

可以先從這句話入手這題『我們嘗試走到底,在一層一層數回來』,也就是所謂的recursive的概念。

  1. 所以要如何走到底呢,我們要先有一個function => dfs,他可以判斷left跟right是否有node

2. 在此 dfs function 裡面,我們在呼叫一次dfs,他自然就開始往下走

3. 每次 dfs 走完,我們都要回傳他自己+再往下的深度。因為我們假設是走到底,如果left跟right都沒有 node,則回傳1(自己的 node)。假設是倒數第二層,則是自己1+最後一層的深度(1)=> 2

/**
 * 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 depth = 0
    
    if(root != null){
        depth = 1 + dfs(root.left,root.right)
    }
    
    return depth
    
    function dfs(l, r){
        
        let leftDepth = 0
        
        if(l != null){
            leftDepth = 1 + dfs(l.left, l.right)
        }
        
        let rightDepth = 0
        
        if(r != null){
            rightDepth = 1 + dfs(r.left, r.right)
        }
        
        if(leftDepth >= rightDepth) return leftDepth
        
        if(rightDepth > leftDepth) return rightDepth
        
    }
    
    
};

Leave a Comment

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