力扣105从前序和中序遍历序列构造二叉树

直达链接

其实这个题在笔试卷考选择题出现挺多的，学《数据结构预算法》专业课习题也有，但是确实是不熟悉了

理论，重构二叉树

前序、中序和后序

二叉树的前序、中序、后序遍历

一种非常简单的中序遍历实现，通过递归实现的深度优先遍历

前序和后序只需要改变递顺序就行

class Solution {
public:
vector inorderTraversal(TreeNode* root) {
vector ret;
dps(ret,root);
return ret;
}
void dps(vector& ret,TreeNode* root){
if(root==nullptr) return;
dps(ret,root->left);
ret.push_back(root->val);
dps(ret,root->right);
}
};


前序+后序

• 前序+后序无法构造出唯一的二叉树

前序+中序

1. 前序遍历的第一位数字一定是这个二叉树的根节点


2. 中序遍历中，根节点将序列分为了左右两个区间


3. 递归上面的步骤，构建二叉树

第一遍，跟着敲，理解

class Solution {
private:
// 使用哈希映射快速定位
unordered_map index;
public:
TreeNode* myBuildTree(const vector& preorder, const vector inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
// 参数：索引，0，n-1
if (preorder_left > preorder_right) {
return nullptr;
}
// 为什么要加这一句判断？什么情况下会出现？递归的参数中可能会出现
int preorder_root = preorder_left;// 前序遍历第一个就是根节点，这里是索引位置
int inorder_root = index[preorder[preorder_root]];// 根据根节点值找到它在中序序列中的索引位置
// 开始构建树，创建根节点并赋初值
TreeNode* root = new TreeNode(preorder[preorder_root]);
int size_left_subtree = inorder_root - inorder_left;// 拿两个索引位置相减
// 递归地构造左子树，并连接到根节点
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector& preorder, vector& inorder) {
int n = preorder.size();
for (int i = 0; i // 以中序遍历中的元素为键，值为在中序遍历中的索引位置
// 相当于把中序序列的键值倒转
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};


空间效率非常差，时间效率也不好

我觉得是为了让算法清晰易懂才这么写的，肯定有效率更高的做法

分析

数据结构上使用了一个哈希映射，用于在从前序序列中得到根节点值后，快速找到在中序序列中根节点的索引位置

而不管是前序左、前序右、中序左、中序右、前序根、中序根，都是为了递归函数服务的

递归过程本身就完美契合树的结构

递归函数每一次执行都会创建一个根节点，并且连接它的两个子节点（如果有的话）

后序+中序

1. 后序遍历的最后一位数字是根节点


2. 中序遍历中，找到根节点位置，划分左右子树 ，递归构建二叉树