(第28天)【leetcode题解】104、二叉树的最大深度 559、N叉树的最大深度 111、二叉树的最小深度

目录

• 104、二叉树的最大深度
• • 题目描述
  • 思路
  • 代码
• 559、N叉树的最大深度
• • 题目描述
  • 思路
  • 代码
• 111、二叉树的最小深度
• • 题目描述
  • 思路
  • 代码

104、二叉树的最大深度

题目描述

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

思路

1. 递归法:

• 返回值：int，返回深度
• 参数：node，传入节点
• 终止条件：node==NULL
• 递归逻辑：后序遍历，左右中

2. 回溯法：

• 返回值：void，在函数内修改深度
• 参数：node节点，depth当前深度(root节点深度为1)
• 终止条件：node的左右子节点都为NULL时
• 递归逻辑：前序遍历，先处理当前节点的深度，在向左向右递归遍历

3. 迭代法：

• 层序遍历：二叉树的最大深度就是最大的层数，只需要在每次遍历一层时把深度加一即可
• 数据结构：使用队列实现层序遍历

代码

递归法：

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == nullptr) return 0;//终止条件
        int left_depth = getDepth(node -> left);//左
        int right_depth = getDepth(node -> right);//右
        return max(left_depth, right_depth) + 1;
    }

    int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
};

回溯法：

class Solution {
public:
    int res;
    void getDepth(TreeNode* node, int depth) {
        res = depth > res ? depth : res;//中

        if (node->left == nullptr && node->right == nullptr) return;

        if (node->left) {//左
            depth++;//递归遍历
            getDepth(node->left, depth);
            depth--;//回溯
        }

        if (node->right) {//右
            depth++;//向下递归遍历
            getDepth(node->right, depth);
            depth--;//回溯
        }

        return;
    }
    int maxDepth(TreeNode* root) {
        res = 0;
        if (root == nullptr) return res;
        getDepth(root, 1);
        return res;
    }
};

迭代法：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            depth++;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

559、N叉树的最大深度

题目描述

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔

思路

递归法：

• 返回值：int最大深度
• 参数： root节点(从根节点进入)
• 终止条件：节点为空时
• 递归逻辑：对于每个节点，都从左到右的进行深度优先遍历(后序遍历)

迭代法：

• 层序遍历：每遍历一层，深度加一。
• 数据结构：队列
• 遍历逻辑：每次遍历，把当前层的节点逐个取出，同时把当前层节点的子节点加入队列

代码

递归法：

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) return 0;
        int depth = 0;
        for (int i = 0; i < root->children.size(); i++) {
            depth = max(depth, maxDepth(root->children[i]));//递归遍历
        }
        return depth + 1;//递归更新
    }
};

迭代法：

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> que;
        if (root != nullptr) que.push(root);
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++;
            for (int i = 0; i < size; i++) {//遍历每一层
                Node* node = que.front();
                que.pop();
                for (int j = 0; j < node->children.size(); j++) {//把每一层所有节点的子节点加入队列
                    if (node->children[j]) que.push(node->children[j]);
                }
            }
        }
        return depth;
    }
};

111、二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

思路

递归法：

• 参数：root节点
• 返回值：int深度
• 终止条件：节点为空时
• 递归逻辑：左子树为空，右子树不为空时，最小深度为1+右子树的深度；右子树为空，左子树不为空时，最小深度为1+左子树的深度；两个子树都不为空时，最小深度为1+两个子树中的最小深度

迭代法：

• 层序遍历：一层一层遍历
• 数据结构：队列
• 判断最小深度的终止条件：当一个节点没有左右子节点，表示遇到了叶子节点，该节点所在层数就是最小层数

代码

递归法：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;//终止条件
        int leftDepth = minDepth(root->left);//左
        int rightDepth = minDepth(root->right);//右
        //中
        //左子树为空，右子树不为空
        if (root->left == nullptr && root->right != nullptr) return 1 + rightDepth;
        //右子树为空，左子树不为空
        if (root->right == nullptr && root->left != nullptr) return 1 + leftDepth;
        //两个子树都不为空
        return 1 + min(leftDepth, rightDepth);
    }
};

迭代法：

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != nullptr) que.push(root);
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (node->left == nullptr && node->right == nullptr) return depth;//最小深度判断条件
            }
        }
        return depth;
    }
};