1. 已知前序和中序遍历能重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回二叉树的后序遍历Postorder = [15, 7, 9, 20, 3]

限制：

0 <= 节点个数 <= 5000

递归

本题直接利用的是二叉树先序遍历和中序遍历的特点，通过递归来求解出答案。 1、通过前序遍历，拿到第一个节点，即为二叉树根节点； 2、利用该根节点，算出左子树节点数量，右子树节点数量； 3、利用数量和根节点在中序节点中遍历，分别算出当前二叉树左右子树的对应先序遍历列表和中序遍历列表； 4、递归求解；

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: map<int, int> dis; //巧妙借助了map，提高检索性能，缩短时间 public: void PostorderTraversal(vector<int>& preorder, vector<int>& inorder) { for(int i = 0; i < inorder.size(); i++){ dis[inorder[i]] = i; } //第一步存map，优化检索 TreeNode* root = dfs(preorder, 0, preorder.size(), inorder, 0, inorder.size()); //第二步递归重建二叉树(关键！) Postorder(root); //第三步递归后序遍历二叉树 } TreeNode* dfs(vector<int>& preorder, int preBegin, int preEnd, vector<int>& inorder, int inBegin, int inEnd){ if(preBegin >= preEnd || inBegin >= inEnd){ return nullptr; } TreeNode* root = new TreeNode(preorder[preBegin]); int index = dis[preorder[preBegin]]; root->left = dfs(preorder, preBegin+1, preBegin+1+(index-inBegin), inorder, inBegin, index); root->right = dfs(preorder, preBegin+1+(index-inBegin), preEnd, inorder, index+1, inEnd); return root; } void Postorder(TreeNode* root){ if(root == NULL) return; Postorder(root->left); Postorder(root->right); cout<<root->val<<' '; } };

2. 已知前序和后序遍历不能重建二叉树

已知前序遍历结果和后序遍历结果，是不能确定一颗二叉树。

前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。

比如：前序序列1、3、6和 后序序列6、3、1。可以确定1是根节点，但是接下来的结果可能是多种的

3. 已知中序和后序遍历能重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

中序遍历 inorder = [9,3,15,20,7]

后序遍历Postorder = [15, 7, 9, 20, 3]

返回二叉树的前序遍历 preorder = [3,9,20,15,7]

限制：

0 <= 节点个数 <= 5000

递归

本题直接利用的是二叉树中序遍历和后序遍历的特点，通过递归来求解出答案。

根据后序序列的最后一个元素建立根结点；在中序序列中找到该元素，确定根结点的左右子树的中序序列；在后序序列中确定左右子树的后序序列；由左子树的后序序列和中序序列建立左子树；由右子树的后序序列和中序序列建立右子树。 #include <bits/stdc++.h> using namespace std; struct Tree{ int val; Tree* left; Tree* right; Tree(int val) : val(val), left(NULL), right(NULL) {} }; int n; int in[31], post[31]; Tree* build_Tree(int inBegin, int inEnd, int postBegin, int postEnd){ if(inBegin >= inEnd || postBegin >= postEnd){ return NULL; } Tree* root = new Tree(post[postEnd-1]); int index = 0; for(int i = 0; i < n; i++){ if(post[postEnd-1] == in[i]){ index = i; break; } } root->right = build_Tree(index+1, inEnd, postEnd-(inEnd-index), postEnd-1); root->left = build_Tree(inBegin, index, postBegin, postEnd-(inEnd-index)); return root; } void printf_postTree(Tree * root){ if(root == NULL) return; cout<<root->val<<' '; printf_postTree(root->left); printf_postTree(root->right); return; } int main(){ //第一步输入 cin>>n; for(int i = 0; i < n; i++){ cin>>in[i]; } for(int i = 0; i < n; i++){ cin>>post[i]; } //第二步根据已知，建议一颗二叉树 Tree* root = build_Tree(0, n, 0, n); //第三步递归，求前序遍历 printf_postTree(root); return 0; }