重建二叉树

重建二叉树 - 遍历二叉树的三种方式

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例：

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

限制：

0 <= 节点个数 <= 5000

二叉树的三种遍历方式

前序遍历，又称为先根遍历(DLR)
中序遍历(LDR)
后续遍历(LRD)(本题没有用到)
先序遍历序列[pre_start:pre_end]
中序遍历序列区间[ino_start;ino_end]

这个题的解法是根据先序遍历和中序遍历的规律，在先序遍历的序列中，因为第一个节点一定是根节点cur_root，所以在中序遍历中寻找这个根节点的位置pos，然后以pos为中点，把中序遍历的序列分为两部分：左子树[ino_start:pos-1]、右子树[pos+1:ino_end](相当于把一棵树的根砍掉，分成了两棵树)，然后根据pos在原来先序遍历的系列中，也把先序遍历的序列分为两部分：左子树[start+1:pos]、右子树[pos:end]。由此把一个大问题分成了两个子问题，分别在左子树和右子树重复该操作。

解法

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){ 
    // 明白DLR LVR的意义所在。
    // 先序遍历的第一个节点是根节点
    struct TreeNode *node = malloc(sizeof(struct TreeNode));
    // 记录根节点在中序遍历中的位置
    int pos;
    int pre_num = 0;
    // 如果树节点是0个，返回NULL
    if(preorderSize == 0) return NULL;
    while(pre_num < preorderSize){ 
        if(inorder[pre_num] == *preorder){ 
            pos = pre_num;
            break;
        }
        pre_num++;
    }
    node->val = *preorder;
    node->left = buildTree(preorder+1,pre_num,inorder,pre_num);
    node->right = buildTree(preorder+pos+1,preorderSize-pre_num-1,inorder+pos+1,preorderSize-pre_num-1);
    return node;
}