代码随想录算法训练营第十六天 | 104.二叉树的最大深度、559.n叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数

���念解析

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）【前序】
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）【后序】
• 根节点的高度就是二叉树的最大深度

  104.二叉树的最大深度

  一、题目详情

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

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

  示例 1：

  输入：root = [3,9,20,null,null,15,7]输出：3

  示例 2：

  输入：root = [1,null,2]输出：2

  提示：

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 left))+1; //return max(maxDepth(root->left),maxDepth(root->right))+1; }};//详细版代码/*class solution {public: int getdepth(TreeNode* node) { if (node == NULL) return 0; int leftdepth = getdepth(node->left); // 左 int rightdepth = getdepth(node->right); // 右 int depth = 1 + max(leftdepth, rightdepth); // 中 return depth; } int maxDepth(TreeNode* root) { return getdepth(root); }};*/

            前序递归

    /** * Definition for a binary tree node. * 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) {} * }; */class Solution {public:    int result;    void getdepth(TreeNode* node, int depth) {        //在开头结算当前最大深度        result = depth > result ? depth : result; // 中        //继续往下走        if (!node->left && !node->right) return ;   //走不下去了，递归出口        if (node->left) { // 左            getdepth(node->left, depth + 1);    //当前深度加上这一层访问的根结点的深度            }        if (node->right) { // 右            getdepth(node->right, depth + 1);    //当前深度加上这一层访问的根结点的深度        }        return ;    }    int maxDepth(TreeNode* root) {        result = 0;        if (!root) return result;        getdepth(root, 1);        return result;    }};

    559.n叉树的最大深度

     一、题目详情

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

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

    N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

    示例 1：

    输入：root = [1,null,3,2,4,null,5,6]输出：3

    示例 2：

    输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]输出：5

    提示：

    • 树的深度不会超过 1000 。
    • 树的节点数目位于 [0, 104] 之间。

      二、解题思路

              跟二叉树最大深度一样，要比较的子树变成最多为n。递归用后序、前序，迭代用层次遍历。

      三、解题代码

      后序递归

      /*// Definition for a Node.class Node {public:    int val;    vector children;    Node() {}    Node(int _val) {        val = _val;    }    Node(int _val, vector _children) {        val = _val;        children = _children;    }};*/class Solution {public:    int maxDepth(Node* root) {        if (root == NULL)            return 0;        int res = 0;        int Size = root->children.size();        for(int i = 0; i children[i]),res);        }        return res + 1;    }};

      前序递归

      /*// Definition for a Node.class Node {public:    int val;    vector children;    Node() {}    Node(int _val) {        val = _val;    }    Node(int _val, vector _children) {        val = _val;        children = _children;    }};*/class Solution {public:    int result;    void getDepth(Node* root, int dep) {        // 前序是中左右，也就在一开头（子树根结点处）进行深度的比较和筛选        result = dep > result ? dep : result;        // 然后就开始访问root的孩子        if (!root->children.size()) { // 没有孩子            return;                   //不用访问了，出口        }        for (int i = 0; i children.size(); i++) { // 逐个访问孩子            getDepth(root->children[i], dep + 1);        }    }    int maxDepth(Node* root) {        if (root == NULL)            return 0;        result = 0;        getDepth(root, 1);        return result;    }};

      层序迭代

      /*// Definition for a Node.class Node {public:    int val;    vector children;    Node() {}    Node(int _val) {        val = _val;    }    Node(int _val, vector _children) {        val = _val;        children = _children;    }};*/class Solution {public:    int maxDepth(Node* root) {        if (root == NULL)            return 0;        int res=0;        queue n;        n.push(root);        while(!n.empty()){    // 队列不为空            int t = n.size();    // 获取当前层数的节点个数            for(int i = 0; ichildren.size();j++){                    n.push(temp->children[j]);                }            }             res++;    // 层数计数        }        return res;    }};

      111.二叉树的最小深度

      一、题目详情

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

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

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

      示例 1：

      输入：root = [3,9,20,null,null,15,7]输出：2

      示例 2：

      输入：root = [2,null,3,null,4,null,5,null,6]输出：5

      提示：

      • 树中节点数的范围在 [0, 105] 内
      • -1000 right) return minDepth(root->left) + 1; else if (root->right && !root->left) return minDepth(root->right) + 1; else return min(minDepth(root->left), minDepth(root->right)) + 1; }};

        前序递归

        /** * Definition for a binary tree node. * 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) {} * }; */class Solution {public:    int result;    void getDepth(TreeNode* root, int dep) {        if (!root) // 走到叶子节点            return;        if (!root->left && !root->right)            result = result > dep ? dep : result;        if (root->left)            getDepth(root->left, dep + 1);        if (root->right)            getDepth(root->right, dep + 1);        return;    }    int minDepth(TreeNode* root) {        if (!root)            return 0;        result = INT_MAX;        getDepth(root, 1);        return result;    }};

        层序迭代

        /** * Definition for a binary tree node. * 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) {} * }; */class Solution {public:    int minDepth(TreeNode* root) {        if (!root)            return 0;        int res = 1;        queue Q;        Q.push(root);        while (!Q.empty()) {            int s = Q.size();            for (int i = 0; i left && !temp->right) //找到了叶结点                    return res;                if (temp->left)                    Q.push(temp->left);                if (temp->right)                    Q.push(temp->right);            }            res++;        }        return res;    }};

        222.完全二叉树的节点个数

        一、题目详情

        给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

        完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

        示例 1：

        输入：root = [1,2,3,4,5,6]输出：6

        示例 2：

        输入：root = []输出：0

        示例 3：

        输入：root = [1]输出：1

        提示：

        • 树中节点的数目范围是[0, 5 * 104]
        • 0 right; int ldepth = 0, rdepth = 0; // 求最左最右结点深度 while (ltemp) { ltemp = ltemp->left; ldepth++; } while (rtemp) { rtemp = rtemp->right; rdepth++; } if (ldepth == rdepth) { // 是满二叉树 return pow(2, ldepth + 1) - 1; } // 非满二叉树 return countNodes(root->left) + countNodes(root->right) + 1; }};

          层次迭代（通用方法）

          /** * Definition for a binary tree node. * 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) {} * }; */class Solution {public:    int countNodes(TreeNode* root) {        if (!root)            return 0;        int result = 0;        queue Q;        Q.push(root);        while (!Q.empty()) {            int s = Q.size();            for (int i = 0; i left)                    Q.push(temp->left);                if (temp->right)                    Q.push(temp->right);                result++;            }        }        return result;    }};