104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
思路：
从底部开始，逐个加1后返回上层
看完代码随想录之后的思路：
因为是算最大深度，所以可以等同于算根部的高度，用后序遍历，逐个加一后返回上层
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL)return 0;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
int depth=max(left,right)+1;
return depth;
}
};收获：
算高度：一般采用后续遍历，因为越靠近根部，高度越高
算深度：一般采用前序遍历，因为越靠近根部，深度越浅
正常的前序算深度，需要用到回溯，后面再补
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
思路：
类似最大的深度，在左右算完之后，在中间取最小。（但是会出现空节点算最小的情况）
看完代码随想录之后的思路：
在最后中节点计算时，需要首先排除空节点的情况。
class Solution {
public:
int minDepth(TreeNode* root) {
if(root==NULL)return 0;
int left_depth=minDepth(root->left);
int right_depth=minDepth(root->right);
int depth=0;
if(root->left==NULL&&root->right!=NULL)depth=1+right_depth;
else if(root->left!=NULL&&root->right==NULL)depth=1+left_depth;
else depth=1+min(left_depth,right_depth);
return depth;
}
};遇到的困难：
二叉树递归就是要向左向右遍历，不存在向左向右递归会漏的情况，所以不用纠结。
判断空节点不是只有根节点才会有这个情况，是所有节点都会存在这个情况，所以可以写在递归的函数中，整体作为中节点的代码。
判断空节点后，不只是选择不空的子树，还需要在子树节点的基础上加1返回
//补充一段官方的代码，重点看看判断空节点后的操作
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int leftDepth = getDepth(node->left); // 左
int rightDepth = getDepth(node->right); // 右
// 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) {
return 1 + rightDepth;
}
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) {
return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};收获：
在前面return执行的话，就不会执行下面的代码了，相当于一个else if
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
思路：
后续遍历逐个加一
看完代码随想录之后的思路：
因为是完全二叉树，所以可以利用从左到右不断的特性，来判断是否为满二叉树，如果是满二叉树，使用2^n-1的方法会极大地减少运算时间
class Solution {
public:
int countNodes(TreeNode* root) {
if(root==NULL)return 0;
TreeNode* left=root->left;
TreeNode* right=root->right;
int left_num=0;
int right_num=0;
while(left){
left=left->left;
left_num++;
}
while(right){
right=right->right;
right_num++;
}
if(left_num==right_num)return (2<<left_num)-1;
else{
left_num=countNodes(root->left);
right_num=countNodes(root->right);
return left_num+right_num+1;
}
}
};收获：
位移操作的优先级小于加减，所以位运算要加括号
重点：
先算左节点和右节点的数量是否相等，不相等之后要用递归。前面判断的操作相当于剪枝，递归的核心部分在最后的else中（因为前面用了return，所以这里可以不用else，直接接在下面写就可以）