【算法刷题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++;    // 深度+1getdepth(node->left, depth);depth--;    // 回溯，深度-1}if (node->right) { // 右depth++;    // 深度+1getdepth(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;}
};