這是什麼

Tree 的一種演算法，DFS 的精神是，找尋的順序是隨著子節點，一層一層往下找，直到碰觸 Leaf 確認沒找到後，回到父節點，此時，如果有其他子節點，那繼續深入該子節點直到 Leaf。重複這些行為直到找到或是所有節點都搜尋過。

首先想像有一個樹長這樣子：

如果是 BFS，會這樣搜尋：

A -> B -> D -> H -> I -> E -> C -> F -> G -> J -> L -> M -> K

這邊是 Stack 大顯身手的場合，每當發現新的節點便放入 Stack 內，每次搜尋的節點是 Stack 的最上面。

刷題：104. 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.

Note: A leaf is a node with no children.

Example:

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

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

思考

參考 DFS 的做法，盡可能遍歷每個 Leaf 後記錄使第幾層。接著繼續遍歷其他子節點，當遍歷完成後，回傳記錄最深的層數。

解題

JS

/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxDepth = (root) => {
  if (root === null) {
    return 0;
  }

  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

Java

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

C

int max(int a, int b)
{
    if (a > b)
    {
        return a;
    }

    return b;
}

int maxDepth(struct TreeNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

看法

原本寫出一個還行的做法，submit 後發現太慢，觀看其他人的寫法才赫然驚覺，用遞迴配上 Max 並且控制回傳的數字（+1），就可以寫出簡潔的答案。

結論

解完這題後，有感觸的點是我沒有能力在第一時間看出遞迴的寫法。這方面只有多練習才能培養，急不得啊！