本文主要是介绍C++从零开始的打怪升级之路(day46)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是关于一个普通双非本科大一学生的C++的学习记录贴
在此前，我学了一点点C语言还有简单的数据结构，如果有小伙伴想和我一起学习的，可以私信我交流分享学习资料
那么开启正题
今天分享的是关于二叉树的题目
1.从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
这道题是很经典的二叉树题目，原理就是利用前序插入数据，中序判断左右子树，构建二叉树，利用了前序和中序的性质，同时也利用了递归的思想
class Solution {
public:TreeNode* _buildTree(vector<int>&preorder, vector<int>& inorder, int inbegin, int inend, int& prei){//判断是否需要构建if(inbegin > inend)return nullptr;//构建头结点TreeNode* root = new TreeNode(preorder[prei]);//查找分隔点int rooti = inbegin;while(rooti <= inend){if(inorder[rooti] == preorder[prei])break;else++rooti;}//如果有数据递归链接左右子树if(inbegin <= rooti - 1)root->left = _buildTree(preorder, inorder, inbegin, rooti - 1, ++prei);if(rooti + 1 <= inend)root->right = _buildTree(preorder, inorder, rooti + 1, inend, ++prei);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int inbegin = 0, inend = inorder.size() - 1, prei = 0;//原函数无法直接完成递归，借助子函数完成TreeNode* ret = _buildTree(preorder, inorder, inbegin, inend, prei);return ret;}
};这是ac代码
2.从中序与后序遍历蓄力构造二叉树
106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树
这题与上面的题是姊妹题，仅有细微的差别，这里直接给代码
class Solution {
public:TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int inbegin, int inend, int& posti){//判断是否需要构建if(inbegin > inend)return nullptr;//创建头结点TreeNode* root = new TreeNode(postorder[posti]);//查找分隔点int rooti = inbegin;while(rooti <= inend){if(inorder[rooti] == postorder[posti])break;else++rooti;}//递归创建左右子树并链接if(rooti + 1 <= inend)root->right = _buildTree(inorder, postorder, rooti + 1, inend, --posti);if(inbegin <= rooti - 1)root->left = _buildTree(inorder, postorder, inbegin, rooti - 1, --posti);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder){ int inbegin = 0, inend = inorder.size() - 1, posti = postorder.size() - 1;TreeNode* ret = _buildTree(inorder, postorder, inbegin, inend, posti);return ret;}
};这是ac代码
3.二叉树的前序遍历
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
二叉树的三种遍历，在前面的学习都已经很熟悉了，这里我们着重要掌握的是非递归的方法，也是以后面试的一个小难题
这里先给出简单的递归解决办法
class Solution {
public:void _preorderTraversal(TreeNode* root, vector<int>& v){if(root == nullptr)return;v.push_back(root->val);_preorderTraversal(root->left, v);_preorderTraversal(root->right, v);}vector<int> preorderTraversal(TreeNode* root) { vector<int> v;_preorderTraversal(root, v);return v;}
};那么，非递归方法要如何求解呢，首先我们要明白，非递归方法是利用迭代来实现的，但其原理还是根据递归的办法来解决的，实际运用中，递归由于要不停的创建函数栈帧，有效率损耗（实际上优化后，时间差的并不多），以及可能导致栈溢出，所以我们才需要掌握非递归办法
非递归办法要创建一个stack，push进vector同时，入栈，在栈内模拟递归
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* cur = root;while(cur || !st.empty()){while(cur){st.push(cur);v.push_back(cur->val);cur = cur->left;}TreeNode* top = st.top();st.pop();cur = top->right;}return v;}
};这是ac代码
4.二叉树的中序遍历
94. 二叉树的中序遍历
和前序遍历如出一辙，这里直接给出递归代码，以及非递归代码
a.递归方法
class Solution {
public:void _inorderTraversal(TreeNode* root, vector<int>& v) {if(root == nullptr)return;_inorderTraversal(root->left, v);v.push_back(root->val);_inorderTraversal(root->right, v);}vector<int> inorderTraversal(TreeNode* root) {vector<int> v;_inorderTraversal(root, v);return v;}
};b.非递归方法
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* cur = root;while(cur || !st.empty()){while(cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();v.push_back(top->val);cur = top->right;}return v;}
};
5.二叉树的后序遍历
和上面的题相似，但是后序遍历要更复杂一点，因为要最后读取根，所以我们要记录读取的值，判断是否遍历完了子树再对根进行读取
class Solution {
public:void _postorderTraversal(TreeNode* root, vector<int>& v){if(!root)return;_postorderTraversal(root->left, v);_postorderTraversal(root->right, v);v.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> v;_postorderTraversal(root, v);return v;}
};class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* cur = root;TreeNode* last = nullptr;while(cur || !st.empty()){while(cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();if(top->right == nullptr || last == top->right){st.pop();last = top;v.push_back(top->val);}else{cur = top->right;}} return v;}
};这是ac代码
新手写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！
这篇关于C++从零开始的打怪升级之路(day46)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
