如何通过算法练习-day14掌握长尾词的运用技巧？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1138个文字，预计阅读时间需要5分钟。
二叉树+110.+平衡二叉树+题目意：判断一个二叉树是否是高度平衡的二叉树。本题中，一棵高度平衡的二叉树定义为：一个二叉树每个节点的左右两个子树的高度差不超过1。
二叉树
110. 平衡二叉树
题意：给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
示例：
思路：本题我们可以自下而上判断二叉树是否为平衡二叉树，以上图为示例，我们先判断15是不是平衡二叉树，很明显是的，此时就引出了我们递归的终止条件，当root为空时，此时返回0；再判断20节点，发现高度差为0，符合条件，此时的高度变为1+子二叉树的最大高度，此时为2，以此往上判断；而当高度差大于-1时，这时我们就会有新的判断条件，只要有一个子树为-1，那么之后的所有子树都为-1，这样我们在返回主函数判断时，判断的依据也自然就是返回的值是否等于-1
C++代码：
int intDepth(TreeNode* root)
{
if(nullptr==root)//当为空节点时，返回0(即叶子节点之后的节点没有高度)
{
return 0;
}
int leftHeigh=intDepth(root->left);
if(leftHeigh==-1)//当有一个节点高度为-1时，就说明该二叉树已经不是平衡二叉树了，所以之后的节点都会继承-1，最后返回给根节点
{
return -1;
}
int rightHeigh=intDepth(root->right);
if(rightHeigh==-1)
{
return -1;
}
int result=rightHeigh-leftHeigh;
if(result<-1||result>1)//当两高度已经不满足条件时，直接返回-1
{
result =-1;
}
else//两高度差还满足条件，此时根节点高度为1+最大高度
{
result=max(leftHeigh,rightHeigh)+1;
}
return result;
}
bool isBalanced(TreeNode* root) {
return intDepth(root)==-1?false:true;
}
257. 二叉树的所有路径
题意：给你一个二叉树的根节点root，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。
示例：
思路：本题的思路就是使用前序遍历和回溯的方法，先将我们看到的节点加入到给定的数组中，用于记录路径的节点，然后再通过返回条件，让数组中元素以->的方式加入arr中，最后在返回到上一步，找是否有不同路径需要保存
C++代码：
vector<string> arr;
void Allpath(TreeNode* root,vector<int>& tmp)
{
tmp.push_back(root->val);//前序遍历写法
if(nullptr==root->left&&nullptr==root->right)//走到一个路径的末尾了
{
string s;
for(int i=0;i<tmp.size()-1;i++)//将前n-1个节点加入，中间需要到->符号
{
s+=to_string(tmp[i]);
s+="->";
}
s+=to_string(tmp[tmp.size()-1]);//单独添加最后一个节点
arr.push_back(s);
}
if(root->left)//模拟回溯函数，先增加节点，然后删除节点
{
Allpath(root->left,tmp);
}
if(root->right)
{
Allpath(root->right,tmp);
}
tmp.pop_back();
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> tmp;
Allpath(root,tmp);
return arr;
}
404. 左叶子之和
题意：给定二叉树的根节点root，返回所有左叶子之和。
示例：
思路：本题我们需要考虑的是，什么是左叶子？即叶子节点的上一个节点的左孩子，就是左叶子。因此，我们需要使用中序便利的方法，找到左叶子，然后再根据左叶子的判断条件进行相加即可
C++代码：
int sum=0;
void CountLeft(TreeNode* root)
{
if(root->left)//中序遍历写法，我们永远需要的都是左叶子节点，包括右子树，也是左叶子节点
{
CountLeft(root->left);
}
if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr)//判断是否为左叶子
{
sum+=root->left->val;
}
if(root->right)
{
CountLeft(root->right);
}
}
int sumOfLeftLeaves(TreeNode* root) {
CountLeft(root);
return sum;
}
本文共计1138个文字，预计阅读时间需要5分钟。
二叉树+110.+平衡二叉树+题目意：判断一个二叉树是否是高度平衡的二叉树。本题中，一棵高度平衡的二叉树定义为：一个二叉树每个节点的左右两个子树的高度差不超过1。
二叉树
110. 平衡二叉树
题意：给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
示例：
思路：本题我们可以自下而上判断二叉树是否为平衡二叉树，以上图为示例，我们先判断15是不是平衡二叉树，很明显是的，此时就引出了我们递归的终止条件，当root为空时，此时返回0；再判断20节点，发现高度差为0，符合条件，此时的高度变为1+子二叉树的最大高度，此时为2，以此往上判断；而当高度差大于-1时，这时我们就会有新的判断条件，只要有一个子树为-1，那么之后的所有子树都为-1，这样我们在返回主函数判断时，判断的依据也自然就是返回的值是否等于-1
C++代码：
int intDepth(TreeNode* root)
{
if(nullptr==root)//当为空节点时，返回0(即叶子节点之后的节点没有高度)
{
return 0;
}
int leftHeigh=intDepth(root->left);
if(leftHeigh==-1)//当有一个节点高度为-1时，就说明该二叉树已经不是平衡二叉树了，所以之后的节点都会继承-1，最后返回给根节点
{
return -1;
}
int rightHeigh=intDepth(root->right);
if(rightHeigh==-1)
{
return -1;
}
int result=rightHeigh-leftHeigh;
if(result<-1||result>1)//当两高度已经不满足条件时，直接返回-1
{
result =-1;
}
else//两高度差还满足条件，此时根节点高度为1+最大高度
{
result=max(leftHeigh,rightHeigh)+1;
}
return result;
}
bool isBalanced(TreeNode* root) {
return intDepth(root)==-1?false:true;
}
257. 二叉树的所有路径
题意：给你一个二叉树的根节点root，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。
示例：
思路：本题的思路就是使用前序遍历和回溯的方法，先将我们看到的节点加入到给定的数组中，用于记录路径的节点，然后再通过返回条件，让数组中元素以->的方式加入arr中，最后在返回到上一步，找是否有不同路径需要保存
C++代码：
vector<string> arr;
void Allpath(TreeNode* root,vector<int>& tmp)
{
tmp.push_back(root->val);//前序遍历写法
if(nullptr==root->left&&nullptr==root->right)//走到一个路径的末尾了
{
string s;
for(int i=0;i<tmp.size()-1;i++)//将前n-1个节点加入，中间需要到->符号
{
s+=to_string(tmp[i]);
s+="->";
}
s+=to_string(tmp[tmp.size()-1]);//单独添加最后一个节点
arr.push_back(s);
}
if(root->left)//模拟回溯函数，先增加节点，然后删除节点
{
Allpath(root->left,tmp);
}
if(root->right)
{
Allpath(root->right,tmp);
}
tmp.pop_back();
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> tmp;
Allpath(root,tmp);
return arr;
}
404. 左叶子之和
题意：给定二叉树的根节点root，返回所有左叶子之和。
示例：
思路：本题我们需要考虑的是，什么是左叶子？即叶子节点的上一个节点的左孩子，就是左叶子。因此，我们需要使用中序便利的方法，找到左叶子，然后再根据左叶子的判断条件进行相加即可
C++代码：
int sum=0;
void CountLeft(TreeNode* root)
{
if(root->left)//中序遍历写法，我们永远需要的都是左叶子节点，包括右子树，也是左叶子节点
{
CountLeft(root->left);
}
if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr)//判断是否为左叶子
{
sum+=root->left->val;
}
if(root->right)
{
CountLeft(root->right);
}
}
int sumOfLeftLeaves(TreeNode* root) {
CountLeft(root);
return sum;
}