Description

104. Maximum Depth of Binary Tree

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, 10^4].
-100 <= Node.val <= 100

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>

int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0; // 如果節點為空，depth為0
    }
    
    // 計算left, right subtree最大深度
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    
    // 返回left, right subtree中的較大值，加上當前節點的深度（1）
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

// 創建新節點的輔助函數
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //分配memory空間
    node->val = val;//將value傳入參數
    node->left = NULL; // 初始化left subtree為空
    node->right = NULL;// 初始化right subtree為空
    return node;
}

Testing

#include <stdio.h>
#include <stdlib.h>

// 定義一個binary tree node
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0; // 如果節點為空，depth為0
    }
    
    // 計算left, right subtree最大深度
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    
    // 返回left, right subtree中的較大值，加上當前節點的深度（1）
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

// 創建新節點的輔助函數
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //分配memory空間
    node->val = val;//將value傳入參數
    node->left = NULL; // 初始化left subtree為空
    node->right = NULL;// 初始化right subtree為空
    return node;
}

// 測試函數
void testMaxDepth() {
    // 構建測試用範例 [3,9,20,null,null,15,7]
    struct TreeNode* root = createNode(3);
    root->left = createNode(9);
    root->right = createNode(20);
    root->right->left = createNode(15);
    root->right->right = createNode(7);

    int depth = maxDepth(root);
    printf("Maximum Depth of the Tree: %d\n", depth);
}

// 主要測試函數
int main() {
    testMaxDepth();
    return 0;
}