【算法刷题day16】Leetcode:104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

104.二叉树的最大深度 （优先掌握递归）

文档链接：[代码随想录]
题目链接：104.二叉树的最大深度 （优先掌握递归）
状态：ok

题目：
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
注意：
1.暂时只看了递归的方法没有看迭代法
2.后序遍历会比前序遍历简单

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int max = getDepth(root);
        return max;
    }
    int getDepth(TreeNode* root){
        if(root == NULL)return 0;
        int leftDepth = getDepth(root -> left);
        int rightDepth = getDepth(root -> right);
        int maxDepth = 1 + max(leftDepth, rightDepth);
        return maxDepth;
    }
};

class solution {
public:
    int result;
    void getdepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中

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

        if (node->left) { // 左
            depth++;    // 深度+1
            getdepth(node->left, depth);
            depth--;    // 回溯，深度-1
        }
        if (node->right) { // 右
            depth++;    // 深度+1
            getdepth(node->right, depth);
            depth--;    // 回溯，深度-1
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == NULL) return result;
        getdepth(root, 1);
        return result;
    }
};

559.n叉树的最大深度

题目链接：559.n叉树的最大深度

class Solution {
public:
    int maxDepth(Node* root) {
        if(root == NULL)return 0;
        int depth = 0;
        for(int i = 0; i < root -> children.size(); i++){
            depth = max(depth, maxDepth(root -> children[i]));
        }
        return depth + 1;
    }
};

111.二叉树的最小深度

文档链接：[代码随想录]
题目链接：111.二叉树的最小深度
状态：ok

题目：
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
注意：
两边的子树分开求最小值

class Solution {
public:
    int minDepth(TreeNode* root) {
       
        return min(root);
    }
    int min(TreeNode* root){
        if(root == NULL) return 0;
        int leftDepth = min(root -> left);
        int rightDepth = min(root -> right);
        if(root -> left == NULL && root -> right != NULL){
            return 1 + rightDepth;
        }
        if(root -> right == NULL && root -> left != NULL){
            return 1 + leftDepth;
        }
        int result = 1 + std::min(leftDepth, rightDepth);
        return result;
    }
};

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

文档链接：[代码随想录]
题目链接：111.二叉树的最小深度
状态：ok

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

class Solution {
public:
    int countNodes(TreeNode* root) {
        return count(root);
    }
    int count(TreeNode* node){
        if(node == NULL) return 0;
        int leftNum = count(node -> left);
        int rightNum = count(node -> right);
        int cou = leftNum + rightNum + 1;
        return cou;
    }
};