题解 | #重建二叉树#

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree2(vector<int> &pre, int pl, int pr, vector<int> &vin, int vl, int vr) {
        if (pl > pr) {
            return nullptr;
        }
        if (pl == pr) {
            return new TreeNode(pre[pl]);
        }
        int rootval = pre[pl];
        int vinpos = vl;
        for (; vinpos <= vr; ++vinpos) {
            if (vin[vinpos] == rootval) {
                break;
            }
        }
        auto res = new TreeNode(rootval);
        res->left = reConstructBinaryTree2(pre, pl + 1, pl + vinpos - vl, vin, vl, vinpos - 1);
        res->right = reConstructBinaryTree2(pre, pl + vinpos - vl + 1, pr, vin, vinpos + 1, vr);
        return res;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return reConstructBinaryTree2(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
    }
};

思路：碰到树基本都是递归。

先序遍历：根-左-右。所以数组第一个元素一定是根节点。

中序遍历：左-根-右。因为题目保证无重复元素，所以可以根据根节点的值找到中序遍历根节点的位置，再根据中序遍历的顺序，将中序遍历数组分为左子树、根与右子树。

通过中序遍历数组获取了左子树与右子树长度，所以可以将先序遍历数组同样分为根、左子树与右子树。

对左右子树递归建树。