如何通过算法练习-day17掌握长尾词的运用技巧？

本文共计1683个文字，预计阅读时间需要7分钟。

二叉树+110.+平衡二叉树+题目意义：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡的二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

二叉树

110. 平衡二叉树

题意：给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 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; }

513. 找树左下角的值

题意：给定一个二叉树的根节点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; }

112. 路径总和

题意：给你二叉树的根节点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));//统一不计算根节点 }

106. 从中序与后序遍历序列构造二叉树

题意：给定两个整数数组 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; }