LeetCode 104. Maximum Depth of Binary Tree [Easy] [C++] 解題筆記

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.

想法:

        直接做 traversal ，dfs 或是 bfs 並紀錄經過的 node 個數即可。

完整程式碼:

解法一 (DFS):

class Solution {

public:

    int max_depth;

    void dfs(TreeNode* root, int depth) {

        if (root == nullptr) { return; }

        max_depth = max(max_depth, ++depth);

        dfs(root->left, depth);

        dfs(root->right, depth);

        return;

    }

    int maxDepth(TreeNode* root) {

        max_depth = 0;

        dfs(root, 0);

        return max_depth;

    }

};

解法二 (DFS, more concise):

class Solution {

public:

    int maxDepth(TreeNode* root) {

        if (root == NULL) { return 0; }

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

    }

};

解法三 (BFS):

class Solution {

public:

    int maxDepth(TreeNode* root) {

        int depth = 0;

        if (root == NULL) { return depth; }

        queue <pair<TreeNode*, int>> q;

        q.push(make_pair(root, 1));

        while(!q.empty()) {

            auto cur = q.front();

            q.pop();

            auto c_node = cur.first;

            if (c_node->left != NULL) {

                q.push(make_pair(c_node->left, cur.second+1));

            }

            if (c_node->right != NULL) {

                q.push(make_pair(c_node->right, cur.second+1));

            }

            depth = cur.second;

        }

        return depth;

    }

};