105. 从前序与中序遍历序列构造二叉树

[hey-monster]

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

 

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]
 

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：递归
先序遍历的节点为根节点，找到它在中序遍历中的位置，然后递归处理

void initNewNode(struct TreeNode** p, int value){
    (*p) = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    (*p)->val = value;
    (*p)->left = NULL;
    (*p)->right = NULL;
}
int getNewMid(int* inorder, int inorderLeft, int inorderRight, int num){
    for(int i = inorderLeft; i <= inorderRight; ++i){
        if(num == inorder[i]){
            return i;
        }
    }
    return -1;
}
void Dfs(struct TreeNode** current,
            int* preorder, int* inorder, 
            int preorderLeft, int preorderRight,
            int inorderLeft, int inorderRight){
    if(preorderLeft > preorderRight){
        return;
    }
    initNewNode(current, preorder[preorderLeft]);
    int inorderRoot = getNewMid(inorder, inorderLeft, inorderRight, preorder[preorderLeft]);
    if(inorderRoot == -1){
        return;
    }
    int leftSubtreeSize = inorderRoot - inorderLeft;
    Dfs(&(*current)->left, preorder, inorder, preorderLeft + 1, preorderLeft + leftSubtreeSize, inorderLeft, inorderRoot - 1);
    Dfs(&(*current)->right, preorder, inorder, preorderLeft + leftSubtreeSize + 1, preorderRight, inorderRoot + 1, inorderRight);
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    struct TreeNode* root = NULL;
    int size = preorderSize;
    Dfs(&root, preorder, inorder, 0, size - 1, 0, size - 1);
    return root;
}

思路2：迭代
归纳规律，看起来比较麻烦，先不看了