5555 以前的y总会写题解，现在y总不写了 555

多希望能把算法基础的题解写一下，不然太痛苦了

模板

没有用hash，没有看题解独立ac了，开心

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,inorder, 0, preorder.size()-1, 0, inorder.size()-1);
    }

private:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR) {
        if (inL > inR) return nullptr;
        TreeNode* root = new TreeNode(preorder[preL]);
        int idx = 0;
        for (int i = inL; i <= inR; ++i) 
            if (inorder[i] == preorder[preL]) idx = i;
        root->left = build(preorder, inorder, preL+1, preL + (idx - inL), inL, idx-1);
        root->right = build(preorder, inorder, preL + idx + 1 - inL, preR, idx + 1, inR);
        return root;
    }
};

想问下，如果中序遍历存在重复元素，用unordered_map来存放中序遍历元素对应的位置是不是有问题

题目中的限制一般都是有用的，题目中说明了不存在重复元素。

哈哈谢谢，没仔细看题目，大佬还没睡呢

正要休息呢

自荐题解： https://www.acwing.com/file_system/file/content/whole/index/content/5684403/
（包括变量说明 + 代码注意点）

为什么这个没有main函数？

我也想知道。。。

剑指offer 的题哇，都没有的吧

来一个只用一个函数的递归，利用有初始值的参数来实现

/**
 * 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 {
public:
    unordered_map<int,int> q;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder,int l=0,int r=-1,int l2=0,int r2=-1) {
        if(r==-1){
            r=r2=preorder.size();
            for(int i=0;i<r;++i) q.insert(unordered_map<int,int>::value_type(inorder[i],i));
        }
        if(l>=r) return NULL;
        TreeNode* root=new TreeNode{preorder[l]};
        root->left=buildTree(preorder,inorder,l+1,l+1+q[preorder[l]]-l2,l2,q[preorder[l]]),root->right=buildTree(preorder,inorder,l+1+q[preorder[l]]-l2,r,q[preorder[l]]+1,r);
        return root;
    }
};

这代码写的真的优雅

这里有图解
https://leetcode.cn/leetbook/read/illustration-of-algorithm/99ljye/

auto left = bfs(preorder, pl+1, pl+k, inorder, il, k-1);
auto right = bfs(preorder, pl+k+1, pr, inorder, k+1, ir);
y总，为啥这样写过不去啊，-il 是干啥呢

同问

https://blog.csdn.net/qq_45638271/article/details/118906295?spm=1001.2014.3001.5501可以看一下这个博客

相对位置

pos[pre[pl]] - il;这句话啥意思

寻找前序的根节点在中序遍历中是在第几个位置

左子树长度

牛

为什么我把边界条件改成if (il > ir)就会出错呢？

我试了一下，改完之后也是正确的。你可能是其他地方写错了。

y总，请问下为什么这种做法在牛客上提交会超出内存限制， 在这里提交不会

我试了一下，上面的代码都可以过。

class Solution(object):
    def buildTree(self, preorder, inorder):
        self.pos = {} 
        self.preorder = preorder
        for i, val in enumerate(inorder):
            self.pos[val] = i
        return self.recur(0, 0, len(inorder) - 1)

    def recur(self, pre_left, in_left, in_right):
        if in_left > in_right: 
            return 
        val = self.preorder[pre_left]
        root = TreeNode(val) 
        k = self.pos[val]    
        left_length = k - in_left
        root.left = self.recur(pre_left + 1, in_left, k - 1) 
        root.right = self.recur(pre_left + 1 + left_length, k + 1, in_right) 
        return root 

棒

中序遍历是不是也需要判断长度是不是为0

由于题目中说明了“数据保证合法”，所以只要前序遍历非空，那么中序遍历也一定非空。

几天前看面经 有 问存在重复元素本题该怎么解得情况- -没想出来 想请教y老师

结果不唯一，当所有数均相同时最多会有指数种答案。所以直接暴搜就行了，没有比这更快的算法了。

dfs函数里传入inorder没用吧

有用，因为 preorder，inorder 是局部变量，每次 dfs都要使用。

public TreeNode buildTree(int[] pre, int[] in) {
        if (pre.length == 0) {
            return null;
        }

        TreeNode node = null;
        for (int i = 0; i < in.length; i++) {
            if (pre[0] == in[i]) {
                node = new TreeNode(pre[0]);
                node.left = buildTree(
                        Arrays.copyOfRange(pre, 1, i + 1),
                        Arrays.copyOfRange(in, 0, i));
                node.right = buildTree(
                        Arrays.copyOfRange(pre, i + 1, pre.length),
                        Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return node;
    }

避免了每次去计算index的值

最坏情况下所有节点的左儿子都为空，那么就会递归 $n$ 层，每层会复制一遍数组，需要 $O(n)$ 的时间，那总共就需要 $O(n^2)$ 的时间了。

输入的前序遍历序列和中序遍历序列不匹配怎么办？

这道题目保证了前序遍历和中序遍历一定是匹配的。如果不匹配我们可以在递归函数开头判断两个序列的长度是否相同，如果不同，则说明不匹配，直接返回即可。

单纯的判断两个序列的长度并不能说明是否匹配吧

每次递归的时候都要判断长度是否相等，如果长度一直都相等，那就说明是匹配的