前言
本篇为二叉树专题的刷题题单，总共7道题，每道题都有对应的链接。
边听歌边刷题吧~
110. 平衡二叉树
链接： 力扣 110. 平衡二叉树
解题思路
- 首先高度平衡的二叉树的定义是一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
- 那么就要求左右子树的高度，而且是每个节点的左右子树
- 不妨另设一个函数getHigh
- 这个函数的作用是：1.求当前节点树的高度 2.判断当前节点的左右子树的高度差是否满足条件
- 可以设置一个标记值 如 -1 ，如果高度差不满足高度平衡的二叉树的定义就返回-1
- 在isBalanced函数检验，是-1就返回false，否则返回true
- getHigh函数碰到没有节点为null返回0
AC代码
class Solution { public: int getHigh(TreeNode* node) { if(node==nullptr)return 0; int leftHigh = getHigh(node->left); if(leftHigh==-1)return -1; int rightHigh = getHigh(node->right); if(rightHigh==-1)return -1; return abs(leftHigh - rightHigh) > 1 ? -1 : 1+max(leftHigh,rightHigh); } bool isBalanced(TreeNode* root) { return getHigh(root) == -1 ? false : true; } };
257. 二叉树的所有路径
链接： 257. 二叉树的所有路径
解题思路
- 想要求所有到叶子节点的路径就要遍历
- 选择前序遍历，原因是其他遍历不满足条件【可自己尝试】
- 确定参数：当前节点、当前路径、结果集合
- 终止条件：当自己是叶子节点，也就是左右节点为空时，结果添加当前路径
- 访问节点要放在终止条件前面，因为这样它才是完整路径
- 如果有左节点：访问左节点下的路径
- 再删除path中的当前节点，回退到上一节点
- 如果有右节点：访问右节点下的路径
- 再删除path中的当前节点，回退到上一节点
AC代码
class Solution { public: //转换为标准格式 string Trans(vector<int>&path) { int n=path.size(); string ans; for(int i=0;i<n;++i) { ans+=to_string(path[i]); ans+="->"; } int len=ans.size(); ans=ans.substr(0,len-2); return ans; } void TravelPath(TreeNode* node,vector<int>&path,vector<string>&result) { path.push_back(node->val); if(node->left==nullptr&&node->right==nullptr) { string tmpath = Trans(path); result.push_back(tmpath); return; } if(node->left){ TravelPath(node->left,path,result); path.pop_back(); } if(node->right){ TravelPath(node->right,path,result); path.pop_back(); } } vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; if (root == nullptr) return result; vector<int> path; TravelPath(root,path,result); return result; } };
404. 左叶子之和
链接：404. 左叶子之和
解题思路
- 题意是求所有左叶子节点的和
- 所以需要判断是否是左叶子节点
- 我们用一个参数来标志，0为root，1为left，2为right
- 确定参数：当前节点、节点和、标识
- 终止条件：找到叶子节点，判断是否为左叶子节点，更新sum
AC代码
class Solution { public: void SumLeft(TreeNode* node,int&sum,int flag) { if(node->left==nullptr&&node->right==nullptr) { if(flag==1)sum+=node->val; return; } if(node->left)SumLeft(node->left,sum,1); if(node->right)SumLeft(node->right,sum,2); } int sumOfLeftLeaves(TreeNode* root) { if(root==nullptr)return 0; int sum=0; int flag=0;//1为左，2为右 SumLeft(root,sum,0); return sum; }
513. 找树左下角的值
链接：513. 找树左下角的值
解题思路
方法一：层序遍历
- 题目说要找到最底层、最左边的节点，也就是要去最底层
- 想到用层序遍历，只要在队列中保持只有一层的节点
- 然后再在其中选择最左边的节点返回即可
AC代码
class Solution { public: int findBottomLeftValue(TreeNode* root) { queue<TreeNode*> qe; if(root!=nullptr)qe.push(root); int result; while(!qe.empty()) { int size=qe.size(); for(int i=0;i<size;i++) { //怎么判断是最后一层？ //只需要将每一层push_back后 //再在删除节点的同时，push_back它的左右孩子 //这样每次while循环，qe中都只有一层的节点 TreeNode* tmp = qe.front(); qe.pop(); //用一个参数来记录一层中最左边的孩子 if(i==0) result=tmp->val; if(tmp->left)qe.push(tmp->left); if(tmp->right)qe.push(tmp->right); } } return result; } };
方法二：递归
- 使用前序遍历可以最先找到最左边的值
- 此时要判断高度是否为最深
- 若当前深度更大则更新maxh
AC代码
class Solution { public: //maxh当前已知最大深度，curh当前深度 void getLLeftV(TreeNode* node,int &maxh,int curh,int &res) { //终止条件：为叶子节点才可能是最底层，此时判断深度，若当前深度更大则更新maxh if(node->left==nullptr&&node->right==nullptr) { if(curh>maxh) { maxh=curh; res=node->val; } } if(node->left)getLLeftV(node->left,maxh,curh+1,res); if(node->right)getLLeftV(node->right,maxh,curh+1,res); } int findBottomLeftValue(TreeNode* root) { if(root->left==nullptr&&root->right==nullptr)return root->val; //maxh当前已知最大深度，res最左值 int maxh=0, res=0; getLLeftV(root,maxh,0,res); return res; } };
112. 路径总和
链接： 路径总和
解题思路
- 题目要求要找一条路径，它上面的节点的值的和为目标值
- 那么就需要遍历和回溯
- 遍历到每个节点都要加上它的值
- 回溯：退出这个节点就要减去它的值
- 在开始的时候判断是否为叶子节点以及是否达到目标值，是返回true
- 只是节点，不是目标值，返回false
AC代码
class Solution { public: bool IFhasVal(TreeNode* node,int cursum,int targetSum) { if(node->left==nullptr&&node->right==nullptr&&cursum==targetSum) return true; if(node->left==nullptr&&node->right==nullptr) return false; if(node->left) { cursum += node->left->val; if(IFhasVal(node->left,cursum,targetSum))return true; cursum -= node->left->val; } if(node->right) { cursum += node->right->val; if(IFhasVal(node->right,cursum,targetSum))return true; cursum -= node->right->val; } return false; } bool hasPathSum(TreeNode* root, int targetSum) { if(root==nullptr) return false; return IFhasVal(root,root->val,targetSum); } };
106. 从中序与后序遍历序列构造二叉树
解题思路
- 如果只是根据数组来画出树的样子，我相信大家都会
- 不会的参考我的这篇文章☞【二叉树的链式存储讲解及前中后序遍历和层次遍历】
- 再根据这个思路，先找后序数组最后一个点
- 再由这个点将中序数组分为两半
- 左边是左子树，右边是右子树
- 然后将后序数组进行分割
- 将后序数组最后一个节点删除，它已经构建好了
- 因为两个数组表示的是同一个树
- 所以左子树的节点数量相同，也就可以构建后序数组的左右子树数组
- 再递归下去
- 终止条件是到了叶子节点就只返回节点
- 或者到了后序数组大小为0就结束
AC代码
方式一
class Solution { public: TreeNode* travel(vector<int>& inorder, vector<int>& postorder) { if(postorder.size()==0)return nullptr; //根节点 int rootValue = postorder[postorder.size()-1]; TreeNode* root = new TreeNode(rootValue ); //如果是叶子节点就返回root if(postorder.size()==1)return root; //寻找中序遍历的clipdot切割点 int clipdot; for(clipdot=0;clipdot<inorder.size();++clipdot) { if(inorder[clipdot]==rootValue )break; } //开始切割中序数组 //左子树 vector<int> ileftVector(inorder.begin(),inorder.begin()+clipdot); //右子树 vector<int> irightVector(inorder.begin()+clipdot+1,inorder.end()); //把后序数组最后一个节点删除 postorder.resize(postorder.size()-1); //开始切割后序数组 //左子树 vector<int> pleftVector(postorder.begin(),postorder.begin()+ileftVector.size()); //右子树 vector<int> prightVector(postorder.begin()+ileftVector.size(),postorder.end()); root->left = travel(ileftVector,pleftVector); root->right = travel(irightVector,prightVector); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if(inorder.size()==0||postorder.size()==0)return nullptr; return travel(inorder,postorder); } };
方式二
class Solution { private: // 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd) TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) { if (postorderBegin == postorderEnd) return NULL; int rootValue = postorder[postorderEnd - 1]; TreeNode* root = new TreeNode(rootValue); if (postorderEnd - postorderBegin == 1) return root; int delimiterIndex; for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) { if (inorder[delimiterIndex] == rootValue) break; } // 切割中序数组 // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd) int leftInorderBegin = inorderBegin; int leftInorderEnd = delimiterIndex; // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd) int rightInorderBegin = delimiterIndex + 1; int rightInorderEnd = inorderEnd; // 切割后序数组 // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd) int leftPostorderBegin = postorderBegin; int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd) int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin); int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了 root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd); root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd); return root; } public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (inorder.size() == 0 || postorder.size() == 0) return NULL; // 左闭右开的原则 return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size()); } };
二者的思路都是一样的，不过方法二不再新建vector，节省了空间。
105. 从前序与中序遍历序列构造二叉树
解题思路
- 和106一样的思路
- 先确定根节点，再到中序数组将左右子树分辨出来
- 再借此将前序数组的左右子树分辨
- 每一次记得把根节点删除
- 在前序数组空了就返回null，说明到叶子节点了
AC代码
class Solution { public: TreeNode* travel(vector<int>& preorder, vector<int>& inorder) { if(preorder.size()==0)return nullptr; int rootVal=preorder[0]; TreeNode* root = new TreeNode(rootVal); int clipNum;//分割点 for(clipNum = 0;clipNum<=inorder.size();++clipNum) { if(inorder[clipNum]==rootVal)break; } //把前序数组的根节点删除 preorder.erase(preorder.begin()); //把中序数组分为左右子树 vector<int> ileftOrder(inorder.begin(),inorder.begin()+clipNum); vector<int> irightOrder(inorder.begin()+clipNum+1,inorder.end()); //把前序数组分为左右子树 vector<int> pleftOrder(preorder.begin(),preorder.begin()+ileftOrder.size()); vector<int> prightOrder(preorder.begin()+ileftOrder.size(),preorder.end()); root->left=travel(pleftOrder,ileftOrder); root->right=travel(prightOrder,irightOrder); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return travel(preorder, inorder); } };
