leetcode104：二叉树的最大深度

题目链接

leetcode

题目描述

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -101;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    深度优先搜索，递归实现

    1.确定递归函数的参数和返回值
        参数是树的根结点，返回值是这棵树的深度。
    2.确定终止条件
        若树的根结点为空，就返回 0，表示高度为 0。
    3.确定单层递归的逻辑
        先求左子树的深度，再求右子树的深度，最后取左右深度最大值+1。
    
    时间复杂度：O(n)
        其中 n 为二叉树结点的个数，每个结点在递归中只被遍历一次。
    空间复杂度：O(n)
        主要取决于栈的大小，栈中存储了所有未被访问过的结点及其深度。
        在最坏的情况下（当二叉树退化成链表时），栈的大小可能会达到 O(N)。
        在最好的情况下（当二叉树完全平衡时），栈的大小将是 O(logN)。
*/
class Solution_0 {
public:
    // 定义：输入一个结点，返回以该结点为根的二叉树的最大深度
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);

        // 根据左右子树的最大深度，求出该二叉树的最大深度
        return 1 + max(leftMax, rightMax);
    }
};

/*
    广度优先搜索，迭代实现

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int depth = 0;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            depth++;
        }

        return depth;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> root_cases = {
        {3,9,20,NULL_NODE,NULL_NODE,15,7},
        {1,NULL_NODE,2},
    };

    for (const auto& nums : root_cases) {
        cout << "Input: ";
        printArray(nums);

        // 创建二叉树
        TreeNode* root = createTree(nums);
        // 中序遍历
        int result = solution.maxDepth(root);
        cout << "Output: " << result << endl;
        
        // 释放内存
        deleteTree(root);
    }

    return 0;
}