二叉树
题意:给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例:
思路:本题我们可以自下而上判断二叉树是否为平衡二叉树,以上图为示例,我们先判断15是不是平衡二叉树,很明显是的,此时就引出了我们递归的终止条件,当root为空时,此时返回0;再判断20节点,发现高度差为0,符合条件,此时的高度变为1+子二叉树的最大高度,此时为2,以此往上判断;而当高度差大于-1时,这时我们就会有新的判断条件,只要有一个子树为-1,那么之后的所有子树都为-1,这样我们在返回主函数判断时,判断的依据也自然就是返回的值是否等于-1
递归代码:
int BalanceAVL(TreeNode *root)
{
if(nullptr==root)//递归终止条件
{
return 0;
}
int leftheigh=BalanceAVL(root->left);//左子树高度
if(leftheigh==-1)
{
return -1;
}
int rightheigh=BalanceAVL(root->right);//右子树高度
if(rightheigh==-1)
{
return -1;
}
int heighdeffer;//节点最大高度
if(leftheigh-rightheigh>1||leftheigh-rightheigh<-1)
{
heighdeffer=-1;
}
else
{
heighdeffer=1+max(leftheigh,rightheigh);
}
return heighdeffer;
}
bool isBalanced(TreeNode* root) {
return BalanceAVL(root)!=-1?true:false;
}
题意:给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
示例:
思路:本题我们需要确定一个最大深度,因为题目给出的最左下角的值是按深度确定的,准确的是最大深度的最左侧值,因此,上图中的最左下角的值是7,而并非4。所有我们需要遍历每个叶子节点,并且递归终止条件中给出另一个条件去交换最左侧节点的值
递归代码:
int maxheigh=INT_MIN;//最大深度
int leftVal;
void maxLiftVal(TreeNode* root,int tmpheigh)
{
if(nullptr==root->left&&nullptr==root->right)
{
if(maxheigh<tmpheigh)
{
maxheigh=tmpheigh;
leftVal=root->val;
}
return;
}
if(root->left)
{
maxLiftVal(root->left,tmpheigh+1);
}
if(root->right)
{
maxLiftVal(root->right,tmpheigh+1);
}
}
int findBottomLeftValue(TreeNode* root) {
maxLiftVal(root,1);
return leftVal;
}
题意:给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。叶子节点 是指没有子节点的节点。
示例:
思路:本题的思路就是使用递归模拟回溯,减去目标值targetsum,当节点走到叶子节点且targetsum为0时,说明该二叉树有符合条件的路径。
首先,要将目标值统一减去根节点的值,因为每个路径都会包括根节点;其次,我们需要模拟目标值减少的操作,当走到叶子节点发现目标值不为0时,就需要将目标值加回来,然后从另一条路径再次判断。这里我也陷入了一种循环,就是我们在减完目标值后,确实需要立刻判断目标值和所处位置是否满足条件,但是我认为直接在函数中递归判断就行,但是,实际测试发现,还是需要使用if语句作为条件判断依据;这里相当于if语句判断完,整个函数就可以推出了,而继续递归判断的话,只能说明该路径满足,而递归不会停止,所以,此时代码的判断条件就变为了二叉树中,最右边路径之和是否等于目标值。
递归代码:
bool pathRBTree(TreeNode* root,int targetSum)
{
if(nullptr==root->left&&nullptr==root->right)//走到根节点开始判断,是否满足条件
{
if(targetSum==0)
{
return true;
}
return false;
}
if(root->left)
{
targetSum-=root->left->val;//这里模拟的是回溯算法
if(pathRBTree(root->left,targetSum))//减完目标值就需要直接判断是否满足条件
{
return true;
}
targetSum+=root->left->val;
}
if(root->right)
{
targetSum-=root->right->val;
if(pathRBTree(root->right,targetSum))
{
return true;
}
targetSum+=root->right->val;
}
return false;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(nullptr==root)//根节点为空,直接判断错误
{
return false;
}
return pathRBTree(root,targetSum-(root->val));//统一不计算根节点
}
题意:给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例:
思路:本题思路非常简单,就是利用后序遍历的特点,每个后序遍历数组的最后一个元素就是一棵树的根节点,然后再将中序遍历不断分割,这样一直递归下去,即可得到二叉树本来的样子
递归代码:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(postorder.size()==0)//以后序遍历数组为目标,因为每次递归都会移除一个元素
{
return nullptr;
}
int rootval=postorder[postorder.size()-1];//锁定后序遍历最后一个元素,这就是根节点
TreeNode* root=new TreeNode(rootval);
int mid;//找到中序遍历的分割位置
for(mid=0;mid<inorder.size();mid++)
{
if(inorder[mid]==rootval)
{
break;
}
}
postorder.resize(postorder.size()-1);
vector<int> leftinorder(inorder.begin(),inorder.begin()+mid);//分割中序遍历
vector<int> rightinorder(inorder.begin()+mid+1,inorder.end());
vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());//分割后序遍历
vector<int> rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());
root->left=buildTree(leftinorder,leftpostorder);
root->right=buildTree(rightinorder,rightpostorder);
return root;
}
标签:return,int,练习,算法,day17,二叉树,root,节点,targetSum
From: https://blog.51cto.com/u_15209404/6681436