104.二叉树的最大深度 （优先掌握递归）
卡哥建议：什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。大家要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html
做题思路：
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。用什么遍历顺序这里多看卡哥视频理解吧。
先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
本题后序遍历的递归法代码：
1 int getdepth(TreeNode* node) {
2 if (node == NULL) return 0;
3 int leftdepth = getdepth(node->left); // 左
4 int rightdepth = getdepth(node->right); // 右
5 int depth = 1 + max(leftdepth, rightdepth); // 中
6 return depth;
7 }
8 int maxDepth(TreeNode* root) {
9 return getdepth(root);
10 }
111.二叉树的最小深度 （优先掌握递归）
卡哥建议：先看视频讲解，和最大深度 看似差不多，其实 差距还挺大，有坑。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html
做题思路：
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度。注意是叶子节点。什么是叶子节点，左右孩子都为空的节点才是叶子节点！如果根节点的左子树是空的话，那就从右子树开始找叶子节点。
求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
本题后序遍历的递归法代码：
1 int getDepth(TreeNode* node) {
2 if (node == NULL) return 0;
3 int leftDepth = getDepth(node->left); // 左
4 int rightDepth = getDepth(node->right); // 右
5 // 中
6 // 当一个左子树为空，右不为空，这时并不是最低点
7 if (node->left == NULL && node->right != NULL) {
8 return 1 + rightDepth;
9 }
10 // 当一个右子树为空，左不为空，这时并不是最低点
11 if (node->left != NULL && node->right == NULL) {
12 return 1 + leftDepth;
13 }
14 int result = 1 + min(leftDepth, rightDepth);
15 return result;
16 }
17
18 int minDepth(TreeNode* root) {
19 return getDepth(root);
20 }
222.完全二叉树的节点个数（优先掌握递归）
卡哥建议：需要了解，普通二叉树 怎么求，完全二叉树又怎么求
题目链接/文章讲解/视频讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html
做题思路（我从卡哥的文章摘出来一部分）：
普通二叉树先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
在完全二叉树中，底层节点一定是从左边开始连续的，只有左边的也行，只有右边的不行。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
满二叉树的任意节点，要么度为0，要么度为2.换个说法即要么为叶子结点，要么同时具有左右孩子。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。
本题后序遍历的递归法代码：
1 int countNodes(TreeNode* root) {
2 if (root == nullptr) return 0;
3 TreeNode* left = root->left;
4 TreeNode* right = root->right;
5 int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
6 while (left) { // 求左子树深度
7 left = left->left;
8 leftDepth++;
9 }
10 while (right) { // 求右子树深度
11 right = right->right;
12 rightDepth++;
13 }
14 if (leftDepth == rightDepth) {
15 return (2 << leftDepth) - 1; // 这里记住就行，注意(2<<1) 相当于2^2，所以leftDepth初始为0，刚开始也相当于为第0层，就是根节点
16 }
17 return countNodes(root->left) + countNodes(root->right) + 1;
18 }
标签：node,right,int,随想录,二叉树,深度,节点
From： https://www.cnblogs.com/romantichuaner/p/17623850.html