遍历框架
struct TreeNode{int val;TreeNode*left;TreeNode*right;TreeNode():val(0),left(nullptr),right(nullptr){}TreeNode(int x):val(x),left(nullptr),right(nullptr){}TreeNode(int x,TreeNode*left,TreeNode*right):val(x),left(left),right(right){}
};
void dfs(TreeNode*root){//base caseif(root==nullptr){return;}//前序位置dfs(root->left);//中序位置dfs(root->right);//后序位置
}
由遍历结果还原二叉树
-
已知前序遍历结果，中序遍历结果可以构造出唯一二叉树
-
已知后序遍历结果，中序遍历结果可以构造出唯一二叉树
-
已知前序遍历结果，后序遍历结果可以构造出多棵二叉树
由前序，中序还原
-
在前序遍历中 ： 第一个元素是根节点
-
在中序遍历中 ： 根节点对应元素的左侧元素为左子树，右侧元素为右子树
-
根节点易得，就是前序结果的第一个元素
-
然后我们只需在中序结果中定位根节点，就区分出了左子树和右子树
-
至于如何构建左、右子树 ：递归
基于此，我们只需在中序遍历结果中建立值与下标的映射关系,就可以快速定位根节点在中序结果的位置
leetcode 105
class Solution {unordered_map<int,int>val_to_pos;
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n=inorder.size();//在中序结果中建立值与下标的映射for(int i=0;i<n;++i)val_to_pos[inorder[i]]=i;return built(preorder,0,n-1,0,n-1);}TreeNode* built(vector<int>&pre,int preL,int preR,int inL,int inR){//base caseif(preL>preR){return nullptr;}//根节点的值int root_val=pre[preL];//根节点在中序结果的位置int root_pos=val_to_pos[root_val];//左子树大小int siz=root_pos-inL;TreeNode*root=new TreeNode(root_val);//递归建树root->left=built(pre,preL+1,preL+siz,inL,root_pos-1);root->right=built(pre,preL+siz+1,preR,root_pos+1,inR);return root;}
};
图片来源
由后序，中序还原
-
在后序遍历中 ： 最后一个元素是根节点
-
在中序遍历中 ： 根节点对应元素的左侧元素为左子树，右侧元素为右子树
思路和上面几乎一模一样
-
根节点易得，就是后序结果的末尾元素
-
然后我们只需在中序结果中定位根节点，就区分出了左子树和右子树
-
至于如何构建左、右子树 ：递归
基于此，我们只需在中序遍历结果中建立值与下标的映射关系,就可以快速定位根节点在中序结果的位置
leetcode 106
class Solution {unordered_map<int,int>vi;
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n=inorder.size();for(int i=0;i<n;++i){vi[inorder[i]]=i;}return built(postorder,0,n-1,0,n-1);}TreeNode*built(vector<int>&p,int pl,int pr,int il,int ir){if(pl>pr)return nullptr;int v=p[pr];//后序末尾元素是根节点int i=vi[v];int siz=ir-i;//右子树大小TreeNode*root=new TreeNode(v);root->left=built(p,pl,pr-siz-1,il,i-1);root->right=built(p,pr-siz,pr-1,i+1,ir);return root;}
};
图片来源
由前序，后序还原
对于合法的前序遍历和后序遍历
我们可能无法推出唯一的中序结果
换句话说
给你一个前序遍历结果,一个后序遍历结果
我们可以构造出至少一颗二叉树 : 它们都满足这两个遍历结果
例1
preorder : abc
postorder : bca
我们知道
前序遍历结果 = root + 左子树前序结果 + 右子树前序结果
后序遍历结果 = 左子树后序结果 + 右子树后序结果 + root
所以 a 肯定是根节点无疑
同时可以观察出: b一定是a的左孩子,c一定是a的右孩子
所以我们可以构造出唯一一棵二叉树
因为在pre中b紧跟a之后 : 所以b是a的孩子,可能是左孩子或右孩子
但b要想成为a的右孩子,那么在post中它必须紧贴a之前
可是在post中c紧贴a之前,所以b只能是a的左孩子
由于在post中c紧贴a之前,所以c是a的孩子,可能是左孩子或右孩子
但c要想成为a的左孩子,那么在pre中它必须紧跟a之后
可是在pre中b紧跟a之后,所以c只能是a的右孩子
例2
preorder : abc
postorder : cba
按照上面的逻辑,我们可以得到
a 是根节点 , b 是 a 的孩子 , c 是 a 的孩子
但我们无法确定孩子的左右
枚举左右孩子的情况 , 我们可以得到 :
结论
若一个父节点只有一个孩子,那么这个孩子既可以是左孩子,也可以是右孩子
但我们注意到 :
对于pre中紧跟root的那个元素,它可以无条件成为root的左孩子
同理 : 对于post中紧贴root的元素可以无条件成为root的右孩子
尝试构造一种可能解
leetcode 889
我们不妨就令pre中紧跟root的那个元素成为root的左孩子
基于此区分左右区间
图片来源
class Solution {unordered_map<int,int>vi;
public:TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {int n=preorder.size();for(int i=0;i<n;++i)vi[postorder[i]]=i;return built(preorder,0,n-1,0,n-1);}TreeNode*built(vector<int>&pre,int l,int r,int pl,int pr){if(l>r)return nullptr;if(l==r)return new TreeNode(pre[l]);int v=pre[l];int lv=pre[l+1];int i=vi[lv];int siz=i-pl+1;TreeNode*root=new TreeNode(v);root->left=built(pre,l+1,l+siz,pl,i);root->right=built(pre,l+siz+1,r,i+1,pr-1);return root;}
};
但我们显然无法只满足一种可能解,我们可以试着找出所有解
解的个数?
根据上面的结论,对于每一个唯一的孩子,都有左右两种情况
所以解的个数就是 2^n
n = 唯一孩子的个数
系统上讲 : 对pre中的ab,我们尝试在post中找到对应的ba
luogu P1229
#include<iostream>
#include<string>
using namespace std;
int main(){string pre,post;cin>>pre>>post;int ls=pre.length();int cnt=0;for(int i=0;i<ls-1;++i){for(int j=1;j<ls;++j)if(pre[i]==post[j]&&pre[i+1]==post[j-1])cnt++;}cout<<(1<<cnt);//pow (2,cnt)
}
收集所有可能的中序遍历
#include<iostream>
#include<string>
#include<set>
using namespace std;set<string> dfs(string pre, string post) {set<string>ans;int n=pre.size();if(n==0)return ans;if(n==1){ans.insert(pre);return ans;}char root = pre[0];// 只有一个子树if(pre[1]==post[n-2]) {string pre_sub=pre.substr(1);string post_sub=post.substr(0,n-1);auto ans_sub=dfs(pre_sub,post_sub);for(auto x:ans_sub){// 子树作为左子树ans.insert(x+root);// 子树作为右子树ans.insert(root+x);}}// 有两个子树else {char left_root=pre[1];int left_size=0;// 在后序中找到左子树根的位置for(int i=0;i<n;++i){if(post[i]==left_root){left_size=i+1;break;}}string left_pre=pre.substr(1,left_size);string left_post=post.substr(0,left_size);auto ans_left=dfs(left_pre,left_post);string right_pre=pre.substr(1+left_size);string right_post=post.substr(left_size,n-left_size-1);auto ans_right=dfs(right_pre,right_post);for(auto L:ans_left) {for(auto R:ans_right) {ans.insert(L+root+R);}}}return ans;
}int main() {string pre,post;cin>>pre>>post;auto ans=dfs(pre,post);for (auto x:ans){cout<<x<<'\n';}return 0;
}
构造所有满足条件的二叉树
class Solution {unordered_map<int, int> post_pos;
public:vector<TreeNode*> constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {int n = preorder.size();if (n == 0) return {};if (n == 1) return {new TreeNode(preorder[0])};for (int i = 0; i < n; i++) {post_pos[postorder[i]] = i;}return built(preorder, 0, n - 1, postorder, 0, n - 1);}private:vector<TreeNode*> built(vector<int>& pre, int preL, int preR,vector<int>& post, int postL, int postR){vector<TreeNode*>ans;//base caseif (preL > preR) {ans.push_back(nullptr);return ans;}if (preL == preR) {ans.push_back(new TreeNode(pre[preL]));return ans;}int root_val = pre[preL];TreeNode* root = new TreeNode(root_val);// 找到左子树的根节点在前序中的位置int left_root_val = pre[preL + 1];// 在后序中找到左子树根节点的位置int left_root_in_post = post_pos[left_root_val];int left_size = left_root_in_post - postL + 1;// 只有一个子树（左子树或右子树）if (preL + 1 + left_size > preR) {// 只有一个子树（pre[preL + 1] 既可能是左子树也可能是右子树）vector<TreeNode*> left_subtrees = built(pre, preL + 1, preR,post, postL, postR - 1);//作为左子树for (TreeNode* left_tree : left_subtrees) {TreeNode* tree = new TreeNode(root_val);tree->left = left_tree;ans.push_back(tree);}//作为右子树for (TreeNode* right_tree : left_subtrees) {TreeNode* tree = new TreeNode(root_val);tree->right = right_tree;ans.push_back(tree);}} //两个子树else {// 构建左子树的所有可能vector<TreeNode*> left_subtrees = built(pre, preL + 1, preL + left_size,post, postL, left_root_in_post);// 构建右子树的所有可能vector<TreeNode*> right_subtrees = built(pre, preL + 1 + left_size, preR,post, left_root_in_post + 1, postR - 1);// 组合所有可能的左右子树for (TreeNode* left_tree : left_subtrees) {for (TreeNode* right_tree : right_subtrees) {TreeNode* tree = new TreeNode(root_val);tree->left = left_tree;tree->right = right_tree;ans.push_back(tree);}}}return ans;}
};