题解 | #牛群的树形结构重建#

考察知识点： 树的遍历

1. 给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。给出前序和后序遍历序列确定的二叉树结构不唯一。

2. 前序遍历序列、中序遍历序列、后序遍历序列的特点：
   前序遍历序列： [3, 9, 20, 15, 7]，第一个数是根节点，右边依次是左子树和右子树中的节点，左子树的节点和右子树的节点都是分别靠在一起的，但是无法确定这两个子树的分界线。
   中序遍历序列： [9, 3, 15, 20, 7]，如果确定了根节点，那么就能确定左右子树的分界线，明确左右子树中包含哪些节点。
   后序遍历序列： [9, 15, 7, 20, 3]，最后一个数是根节点，左边从左到右依次是左子树和右子树，和前序遍历序列类似。

题目分析：

 根据一段中序遍历序列和后序遍历序列求出原二叉树的结构，可以利用中序遍历序列和后序遍历序列的特征，即先利用后序遍历序列找到根节点，再利用中序遍历序列确定左右子树的分界线（找出左子树和右子树分别有哪些节点）

 例如上述的例子，后序遍历序列是 [9, 15, 7, 20, 3]，中序遍历序列是[9, 3, 15, 20, 7]。首先取后序遍历序列的最后一个数，那么我们得到了整棵树的根节点，他的值是3。然后我们可以通过for循环找到中序遍历序列中值为3的数所在的位置。然后我们就能确定左子树和右子树的节点数量。本例中左子树节点为9,数量为1；右子树节点为15,20,7,数量为3。

 现在我们确定了整棵树的根节点和左右子树的个数，那么该如何继续找到左右子树的根节点以递归地构建一棵树呢？由于后序遍历序列从左到右依次为左子树、右子树、根节点，所以根据左右子树的节点数量，我们就能确定后序遍历序列中哪些节点属于左子树，哪些属于右子树了。本例中左子树： [9, 15, 7, 20, 3]，右子树： [9, 15, 7, 20, 3]。

 而对子树来说，他的后序遍历序列中也是最后一个节点是根节点，中序遍历序列也能找到左右子树的分界线，所以就能递归构建出整棵树。

 注意该算法只适用于二叉树中所有节点的值不同的情况。如果有几个节点的值相同，在中序遍历序列中查找根节点的索引时会出现错误。

所用编程语言： C++

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inOrder int整型vector 
     * @param postOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode *build(vector<int> &inOrder, int inleft, int inright, vector<int> &postOrder, int postleft, int postright) {
        if (inleft > inright) return nullptr;
        auto root = new TreeNode(postOrder[postright]);
        int rootIndex;
        for (int i = inleft; i <= inright; i++) {
            if (inOrder[i] == root->val) {
                rootIndex = i; 
                break;
            }
        }
        root->left = build(inOrder, inleft, rootIndex - 1, postOrder, postleft, postleft + rootIndex - inleft - 1);
        root->right = build(inOrder, rootIndex + 1, inright, postOrder, postleft + rootIndex - inleft, postright - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inOrder, vector<int>& postOrder) {
        // write code here
        int size = inOrder.size();
        if (!size) return nullptr;
        return build(inOrder, 0, size - 1, postOrder, 0, size - 1);
    }
};