04前中后序遍历
# 03 前中后序遍历
前序遍历、中序遍历和后序遍历是三种利用深度优先搜索遍历二叉树的方式。它们是在对节点访问的顺序有一点不同，其它完全相同。例如层次遍历得到的二叉数为 [1,2,3,4,5,6,7]
NLR 其前序遍历结果为 [1,2,4,5,3,6,7]，先遍历父结点，再遍历左结点，最后遍历右节点
void preorder(TreeNode* root) {
visit(root);
preorder(root->left);
preorder(root->right);
}
LNR 其中序遍历结果为[4,2,5,1,6,3,7]，先遍历左节点，再遍历父结点，最后遍历右节点
void inorder(TreeNode* root) {
inorder(root->left);
visit(root);
inorder(root->right);
}
LRN 其后序遍历结果为 [4,5,2,6,7,3,1]，先遍历左节点，再遍历右结点，最后遍历父节点
void postorder(TreeNode* root) {
postorder(root->left);
postorder(root->right);
visit(root);
}
# 144. 二叉树的前序遍历 (opens new window)
实现二叉树的前序遍历
输入一个二叉树，输出一个数组，为二叉树前序遍历的结果
输入：root = [1,null,2,3] 1 \ 2 / 3 输出：[1,2,3]
解析：
二叉树的遍历用递归实现起来很简单，除了递归也可以使用迭代的思路实现，主要就是利用递归的本质就是栈调用，因此可以通过栈来实现二叉树的遍历。
前序遍历是使用迭代思路实现的一种较为简单的情况，将根节点入栈，然后迭代逐层将左右节点入栈。需要注意的是前序遍历中，要注意右节点和左节点的入栈顺序。栈是先入后出的，为了先遍历左节点，让右节点先于左节点入栈，保证左节点先出栈。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root){
return ans;
}
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* node = s.top();
s.pop();
ans.push_back(node->val);
// 栈是先入后出的，所以先右子节点入栈再左子节点入栈，保证左节点先出栈
if(node->right){
s.push(node->right);
}
if(node->left){
s.push(node->left);
}
}
return ans;
}
};
# 145 二叉树的后序遍历 (opens new window)
实现二叉树的后序遍历
输入一个二叉树，输出一个数组，为二叉树后序遍历的结果
输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1]
解析：
二叉树的后序遍历的迭代实现可以直接基于前序遍历实现，因为前序的遍历顺序是 父左右 ，而后序遍历的顺序是 左右父。将前序遍历过程稍作修改就可以得到后序遍历结果：
前序遍历中左右节点入栈顺序为右节点先于左节点，得到的遍历结果为 父左右 。
如果前序遍历中入栈让左节点先于右节点，那么得到的遍历结果就是 父右左 。
将这个得到的遍历结果反转就得到了后序遍历 左右父。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root){
return ans;
}
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* node = s.top();
s.pop();
ans.push_back(node->val);
// 让左节点先于右节点入栈
if(node->left){
s.push(node->left);
}
if(node->right){
s.push(node->right);
}
}
// 将遍历结果反转
reverse(ans.begin(),ans.end());
return ans;
}
};
# 94 二叉树的中序遍历 (opens new window)
实现二叉树的中序遍历
输入一个二叉树，输出一个数组，为二叉树中序遍历的结果
输入：root = [1,null,2,3] 1 \ 2 / 3 输出：[1,3,2]
解析：
迭代实现二叉树的中序遍历要难于前序遍历。根据他们的递归实现可知，前序遍历是自上而下的递归，从根节点处理到子节点，而中序则是从左子树的最左边的叶子节点开始处理，是自下而上的递归。
节点访问过程：由于是自下而上的访问，使用迭代实现中序遍历需要一个额外的指针来访问节点，从根节点一层层向左访问到左子树的最左边的叶子节点并逐个入栈，再开始向上迭代处理节点值。完成访问之后，栈中保存的是从根节点到最左边的叶子节点路径上的所有节点，他们都是左节点。
节点处理过程：直接取栈顶元素将其值加入结果集，然后查看它是否具有右节点。如果有右节点则使用指针从该节点开始进行和根节点一样的访问过程，将从该节点开始到以该节点为根节点的子树的最左叶子节点路径上的所有节点入栈。完成访问之后再重复处理过程，最终完成所有节点的访问和处理。
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root){
return ans;
}
stack<TreeNode*> s;
TreeNode* cur = root;
while(cur || !s.empty()){
if(cur){
// 从根节点到最左叶子节点的访问过程
s.push(cur);
cur = cur->left;
}else{
// 自下而上 左中右的节点处理过程
cur = s.top();
s.pop();
ans.push_back(cur->val);
cur = cur->right;
}
}
return ans;
}
};
# 105 从前序与中序遍历序列构造二叉树 (opens new window)
给定一个二叉树的前序遍历和中序遍历结果，尝试复原这个树。已知树里不存在重复值的节点。
输入是两个一维数组，分别表示树的前序遍历和中序遍历结果；输出是一个二叉树。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
解析：
前序遍历结果+中序遍历结果，或者后序遍历结果+中序遍历结果可以唯一确定二叉树结构。以前序+中序为例，先在前序中从左到右找根节点，然后在中序中找到根节点位置，此时中序中根节点的左侧就是左子树，右侧就是右子树。以preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]为例：
- 前序中找到第一个根节点 3，在中序中区分 3 的左子树长度为 1 包含
9，右子树长度为 3 包含15,20,7 - 前序中找到根节点为 9 的左子树根节点，在中序中发现其左侧为空，右侧为根节点，所以没有左右子树
- 前序中找到根节点为 20 的右子树根节点，在中序中区分 20 的左子树长度为 1 包含
15，右子树长度为 1 包含7 - 前序中找到根节点为 15 的左子树根节点，在中序中发现其左侧长度为0，右侧长度也为0，所以没有左右子树
- 前序中找到根节点为 7 的左子树根节点，在中序中发现其左侧长度为0，右侧为空，所以没有左右子树
- 最终构成了二叉数的层次遍历为
[3,9,20,null,null,15,7]
可以看出根据遍历结果构造二叉树的核心思想就是：在前序或者后序遍历结果中找到根节点，然后在中序遍历中对根节点进行定位找出根节点的左右子树。
在中序遍历中对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。为了便于检索，可以使用哈希表预处理中序遍历的结果，将中序遍历以 <节点值, 中序位置> 存储在哈希表中。
定位根节点之后，构建一个节点，并计算该根节点的左子树节点数目，定义当前根节点子树的左右边界。然后根据边界递归定位其左右子节点。
class Solution {
public:
/*
* leftBound 中序中当前根节点的左子树的最左节点的位置
* rightBound 中序中当前根节点的右子树的最右节点的位置
* rootPreIndex 前序中当前根节点的位置
*/
TreeNode* helper(unordered_map<int,int>& hash, vector<int>& preorder, int leftBound, int rightBound, int rootPreIndex){
if(leftBound > rightBound){
return nullptr;
}
// 根据前序找到中序中根节点的位置，并计算左子树节点数目
int rootVal = preorder[rootPreIndex];
int rootInIndex = hash[rootVal];
int leftLen = rootInIndex - leftBound + 1;
// 构建节点
TreeNode* node = new TreeNode(rootVal);
// 递归构建左右子节点，类似二分查找改变左右边界
// 左子节点为其左子树的根节点，leftBound不变，rightBound变成中序中当前根节点的前一个位置，前序中根节点的后一个节点就是左子数的根节点 rootPreIndex+1
node->left = helper(hash,preorder,leftBound,rootInIndex-1,rootPreIndex+1);
// 右子节点为其右子树的根节点，leftBound变成中序中当前根节点的后一个位置，rightBound不变，前序中根节点跨过左子树节点数目的长度就是右子数的根节点 rootPreIndex+leftLen+1
node->right = helper(hash,preorder,rootInIndex+1,rightBound,rootPreIndex+leftLen);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()){
return nullptr;
}
// 用哈希表预处理中序遍历 <节点值, 中序位置>
unordered_map<int,int> hash;
for(int i=0;i<inorder.size();++i){
hash[inorder[i]] = i;
}
return helper(hash,preorder,0,inorder.size()-1,0);
}
};
# 106 从中序与后序遍历序列构造二叉树 (opens new window)
给定一个二叉树的后序遍历和中序遍历结果，尝试复原这个树。已知树里不存在重复值的节点。
输入是两个一维数组，分别表示树的后序遍历和中序遍历结果；输出是一个二叉树。
输入：中序遍历 inorder = [9,3,15,20,7]，后序遍历 postorder = [9,15,7,20,3]
输出：如下二叉树
3 / \ 9 20 / \ 15 7
解析：
后序+中序和前序+中序本质是没有什么区别，同样采用哈希表预处理中序遍历 <节点值, 中序位置>，然后递归构造二叉树，但是需要注意的是构造过程中，根据后序找到中序中根节点的位置，确定右子树根节点，并计算其右子树节点数目。然后根据右子树数目确定左子树根节点和左右边界。
class Solution {
public:
TreeNode* helper(unordered_map<int,int>& hash, vector<int>& postorder, int leftBound, int rightBound, int rootPostIndex){
if(leftBound > rightBound){
return nullptr;
}
int rootVal = postorder[rootPostIndex];
int rootInIndex = hash[rootVal];
// 计算其右子树节点数目
int rightLen = rightBound - rootInIndex + 1;
TreeNode* node = new TreeNode(rootVal);
// 根据右子树数目确定左子树根节点和左右边界
node->left = helper(hash,postorder,leftBound,rootInIndex-1,rootPostIndex-rightLen);
node->right = helper(hash,postorder,rootInIndex+1,rightBound,rootPostIndex-1);
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(postorder.empty()){
return nullptr;
}
unordered_map<int,int> hash;
for(int i=0;i<inorder.size();++i){
hash[inorder[i]] = i;
}
return helper(hash,postorder,0,inorder.size()-1,postorder.size()-1);
}
};
# 889 根据前序和后序遍历构造二叉树 (opens new window)
给定一个二叉树的前序遍历和后序遍历结果，尝试复原这个树。已知树里不存在重复值的节点。
输入是两个一维数组，分别表示树的前序遍历和后序遍历结果；输出是一个二叉树。
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
解析：
前序+后序，与中序与其中之一组合构造二叉树的区别在于增加的区分左右子树的难度，但是核心思想还是一致的：在前序或者后序遍历结果中找到根节点，然后在另一个遍历结果中找出根节点的左右子树。
前序遍历为：(根结点) (前序遍历左分支) (前序遍历右分支)
后序遍历为：(后序遍历左分支) (后序遍历右分支) (根结点)
假设通过前序找根节点，通过后续确定根节点的左右子树。从根节点开始，假设其左子树包含的节点数目为 leftLen，已知的是该左子树的根节点在前序中是 pre[1]，那么他在后序则是post[leftLen-1]，由此可以得出根节点左子树的数目leftLen = post.indexOf(pre[1]) + 1。所以左子树的范围是post[0:leftLen)；同理，根节点的右子树范围为post[leftLen:post.size()-1)，根节点为post[post.size()-1]。
同样为了便于检索，我们使用哈希表预处理后序遍历的结果，将中序遍历以 <节点值, 中序位置> 存储在哈希表中。
递归过程：定位根节点之后，构建一个节点，并计算该根节点的左子树节点数目，定义当前根节点子树的左右边界。然后根据边界递归定位其左右子节点。值得注意的是递归开始之前要先构造根节点。
class Solution {
public:
TreeNode* helper(unordered_map<int,int> hash, vector<int>& preorder, int leftBound, int rigthBound, int rootPreIndex, int preEnd){
if(rootPreIndex > preEnd){
return nullptr;
}
int rootVal = preorder[rootPreIndex];
TreeNode* node = new TreeNode(rootVal);
// preEnd 就是当前子树在前序序列中最后一个节点所在位置
// 计算之前判断当前节点是否是叶子节点，要先判断否则会越界
if(rootPreIndex+1 > preEnd){
return node;
}
// 根据当前根节点的左节点在后序序列中的位置计算左子树包含的节点数
int leftChildPostIndex = hash[preorder[rootPreIndex+1]];
int leftLen = leftChildPostIndex - leftBound + 1;
// 左子树在后序序列的范围是 [leftBound,leftChildPostIndex]
// 当前根节点的左节点为其前序序列的后一位 rootPreIndex+1
// 左子树在前序序列的最后一个节点是 rootPreIndex+leftLen
node->left = helper(hash,preorder,leftBound,leftChildPostIndex,rootPreIndex+1,rootPreIndex+leftLen);
// 右子树在后序序列的范围是 [leftChildPostIndex+1,rigthBound-1]（减去根节点）
// 当前根节点的右节点为其前序序列的后左子数节点数加一 rootPreIndex+leftLen+1
// 右子树不用考虑其在前序的结束边界
node->right = helper(hash,preorder,leftChildPostIndex+1,rigthBound-1,rootPreIndex+leftLen+1,preEnd);
return node;
}
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
int len = preorder.size();
if(len == 0){
return nullptr;
}
unordered_map<int,int> hash;
for(int i=0;i<len-1;++i){
hash[postorder[i]] = i;
}
return helper(hash,preorder,0,len-1,0,len-1);
}
};