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

知识点

DFS 先序遍历 中序遍历

思路

先序遍历是顺序是“中左右”，中序遍历顺序是“左中右”。因此每次找到对应序列的先序遍历的第一个数作为根节点，然后找到对应的左右子树的对应的范围，把问题化为原问题的子问题，用递归解决。

时间复杂度

最差情况是一条链，时间复杂度为

AC code（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* buildTreeII(vector<int>& preOrder, vector<int>& inOrder) {
        int n = inOrder.size();
        function<TreeNode*(int, int, int, int)> dfs = [&](int l1, int r1, int l2, int r2) {
            auto val = preOrder[l1];
            auto root = new TreeNode(val);
            int len = 0;
            for (int i = l2; i <= r2 and inOrder[i] != val; i ++) {
                len ++;
            }
            if (len > 0) root->left = dfs(l1 + 1, l1 + len, l2, l2 + len - 1);
            if (r1 - l1 - len > 0) root->right = dfs(l1 + len + 1, r1, l2 + len + 1, r2);
            return root;
        };
        return dfs(0, n - 1, 0, n - 1);
    }
};