222. 完全二叉树的节点个数
层序遍历的大框架，在队列里每弹出一个节点，sum++，到最后返回sum
class Solution {
public:
int countNodes(TreeNode* root) {
int sum=0;
queue q;
if(root!=NULL) q.push(root);
while(!q.empty()){
int size=q.size();
for(int i=0;ileft) q.push(node->left);
if(node->right) q.push(node->right);
}
}
return sum;
}
};
110. 平衡二叉树
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数
leetcode中强调的深度和高度很明显是按照节点来计算的。
求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
递归法：
1.明确递归函数的参数和返回值
参数：当前传入节点。
返回值：以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
2.明确终止条件
递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
if(root==NULL) return 0;//终止条件。
3.明确单层递归的逻辑
分别求出其左右子树的高度(提前判断左右子树的高度，如果为-1（即如果节点的左右子树本身不平衡），直接返回-1（即节点肯定不平衡）），然后如果差值小于等于1，则返回当前二叉树的高度（1+max(leftHight,rightHight))，否则则返回-1，表示已经不是二叉平衡树了。
class Solution {
public:
int getHight(TreeNode* root){
if(root==NULL) return 0;//终止条件
//单层循环,分别获取左右子树的高度，如果等于-1（即如果节点的左右子树本身不平衡），直接返回-1（即节点肯定不平衡）
int leftHight=getHight(root->left);
if(leftHight==-1) return -1;
int rightHight=getHight(root->right);
if(rightHight==-1) return -1;
return abs(leftHight-rightHight)>1?-1:1+max(leftHight,rightHight);//获取该节点的左右子树高度差，如果大于1，返回-1（不平衡），否则返回 本身（1）+左右子树的最大高度 作为该节点的高度
}
bool isBalanced(TreeNode* root) {
return getHight(root)==-1?false:true;
}
};
257. 二叉树的所有路径
要求从根节点到叶子节点，因此要用前序遍历，方便父节点指向孩子节点
递归和回溯就是一家的
1.递归函数参数以及返回值
参数：传入的根节点，记录每条路径的path，和存放结果的res
返回值：void
2.确定递归终止条件
当遇到叶子节点时，把路径path放进res中
if(cur->left==NULL && cur->right==NULL){ path转成res的处理}
由于使用了vector 结构path来记录路径，所以要把vector 结构的path转为string格式，再把这个string 放进 res里。
遍历path（注意最后一个元素不用 -> 连接，因此只用遍历到倒数第二个），将path里的int数值转换成string（即to_string)，再用 -> 连接，
3.确定单层递归逻辑
回溯和递归是一一对应的，有一个递归，就要有一个回溯。所以回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里，而我在花括号外！（笑死）。也就是递归完之后，立刻path.pop_back()
class Solution {
public:
void travelsal(TreeNode* cur,vector& path,vector& res){
path.push_back(cur->val);//路径，得先把根放进去
//下面才到叶子节点
//终止条件,就将把路径path放进res中。由于路径path里面装的int数据，res中装的string,因此要将res中的串起来
if(cur->left==NULL && cur->right==NULL){
string spath;
for(int i=0;ileft){
travelsal(cur->left,path,res);
path.pop_back();//回溯
}
if(cur->right){
travelsal(cur->right,path,res);
path.pop_back();//回溯
}
}
vector binaryTreePaths(TreeNode* root) {
vector path;
vector res;
if(root==NULL) return res;
travelsal(root,path,res);
return res;
}
};
404. 左叶子之和
如果左节点不为空，且左节点没有左右孩子，那么这个节点的左节点就是左叶子
递归法：
1.递归函数的参数和返回值
要统计的是左叶子节点之和，那么根节点是一定要传入函数中的，因此传入的参数就是树的根节点。返回值就是数值之和。
2.终止条件
if(root==NULL) return 0;
3.确定单层递归的逻辑
当遇到左叶子节点的时候，记录数值
if(root->left!=NULL && root->left->left==NULL && root->left->right==NULL){//表明遇到左叶子节点
midsum=root->left->val;
}
然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
int Leftsum=sumOfLeftLeaves(root->left);//左
int rightsum=sumOfLeftLeaves(root->right);//右
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
//终止条件
if(root==NULL) return 0;
//单层循环
int sum=0;
int Leftsum=sumOfLeftLeaves(root->left);//左
int rightsum=sumOfLeftLeaves(root->right);//右
//根
int midsum=0;
if(root->left!=NULL && root->left->left==NULL && root->left->right==NULL){//表明遇到左叶子节点
midsum=root->left->val;
}
//左叶子之和
sum=midsum+Leftsum+rightsum;
return sum;
}
};
迭代法：
迭代法就是利用栈
其他的判断条件还是一样的
遇到左叶子节点的判断操作
if(node->left!=NULL && node->left->left==NULL && node->left->right==NULL){
sum+=node->left->val;
}
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
stack st;
if(root==NULL) return 0;
st.push(root);
int sum=0;
while(!st.empty()){
TreeNode* node=st.top();
st.pop();
if(node->left!=NULL && node->left->left==NULL && node->left->right==NULL){
sum+=node->left->val;
}
if(node->left) st.push(node->left);
if(node->right) st.push(node->right);
}
return sum;
}
};
