考察知识点： 树的遍历

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

alt

题目分析：

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

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

alt

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

 计算先序遍历序列中左右子树的起始位置和终止位置时容易出错，需要耐心想想。用中序遍历序列中找到的根节点的索引减去对应左子树的开始位置就是左子树的节点个数。先序遍历序列的开始位置加上节点个数能得到先序遍历序列中左子树的终止位置。如果再加1则得到先序遍历序列中右子树的开始位置。

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

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

所用编程语言： C++

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