110.平衡二叉树
思路
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
即二叉树的最大深度等于根节点的高度，平衡二叉树 是指该树所有节点的左右子树的高度相差不超过1转化为->节点的左右子树最大深度相差不超过1
题解
class Solution {
public:
int getHigh(TreeNode* root)
{
if(root == nullptr)return 0;
return max((getHigh(root->left)+1),(getHigh(root->right))+1);
}
bool isBalanced(TreeNode* root) {
if(root == nullptr)return true;//最后落脚点
if(abs((getHigh(root->left)-getHigh(root->right)))<=1)
return isBalanced(root->left)&&isBalanced(root->right);
return false;
}
};
257.二叉树的所有路径
题目链接：257.二叉树的所有路径
文档讲解：代码随想录
状态：递归结束条件出了一些小问题
思路
本题递归思路很简单，主要问题是vector<string>字符串的处理和终止条件的细节。
注意模拟终止条件，清楚后再编写
学习了to_string()函数的用法
初步了解递归与回溯的细节，递归必有回溯
题解
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(root == nullptr) return res;//最小分化问题到空姐点，res没法初始化
else if(root->left == nullptr && root->right == nullptr)
{//注意模拟递归的终止条件！！！很重要
res.push_back(to_string(root->val));
return res;
}
for(auto &i:binaryTreePaths(root->left))
{//学习了to_string函数
res.push_back(to_string(root->val)+"->"+i);
//回溯的过程
//通俗来说，就是递归从左返回去右时 root->val)+"->"是没有的
}
for(auto &i:binaryTreePaths(root->right))
{
res.push_back(to_string(root->val)+"->"+i);
}
return res;
}
};
404.左叶子之和
思路
首先明确左叶子节点的含义；使用递归分解题目，根节点左叶子节点的和等于左右子树左叶子节点的和（如果有左右子树）
细节1： 怎么知道自己是左叶子？不能等遍历到，因为链表没有指向父节点的指针，我们只能在上一个节点判断，故有root->left!=nullptr && root->left->left== nullptr && root->left->right == nullptr，此条件注意root->left!=nullptr，每次使用节点左右节点的时候一定要注意判断是否为空
细节2： 若当前节点判断了有左叶子，不是return结果，而是保存再处理，因为当前节点还可能有右子树，右子树可能存在左叶子！
题解
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
int result = 0;
if(root == nullptr)return 0;
else if(root->left!=nullptr && root->left->left== nullptr && root->left->right == nullptr)result+=root->left->val;
result+=sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
return result;
}
};
222.完全二叉树的节点个数
题目链接：222.完全二叉树的节点个数
文档讲解：代码随想录
状态：普通树AC，了解了完全二叉树的处理方式
思路
注意完全二叉树与满二叉树的区别：
普通递归遍历不多说，主要记录完全二叉树的性质：
大规模的完全二叉树里面存在的子树很可能是满二叉树，因为完全二叉树的叶子节点全部靠左，所以left_depth==right_depth即可判断满二叉树进而通过2^k-1计算节点
对于非完美二叉树，使用普通遍历即可
题解
// class Solution {
// public:
// int countNodes(TreeNode* root) {
// if(root == nullptr)return 0;
// return 1+countNodes(root->left)+countNodes(root->right);
// }
// };
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == nullptr)return 0;
int leftnum = 0, rightnum = 0;
TreeNode* leftp = root;
TreeNode* rightp = root;
while(leftp!=nullptr)
{
leftp = leftp->left;
leftnum++;
}
while(rightp!=nullptr)
{
rightp = rightp->right;
rightnum++;
}
if(leftnum == rightnum)return (2<<leftnum-1)-1;
return countNodes(root->left)+countNodes(root->right)+1;
}
};