3.4 Construct Binary Tree

• 前序尋訪 1245367 中->左->右
• 中序尋訪 4251637 左->中->右
• 後序尋訪 4526731 左->右->中

如果有中序與前序的追蹤結果或者中序與後序的追蹤結果，可由這些結果求得唯一的二元樹。不過如果只具備前序與後序的追蹤結果就無法決定唯一的二元樹。

這題可以用Divide and Conquer 分治法解，找到root後利用中序結果把樹切左子樹、右子榯

後序+中序 尋訪結果決定唯一的二元樹流程:

1.後序的最後一個數，就是root ,照上面的例子就是

2.在中序425[1]637 , 找出這個1後左邊425就是左子樹，右邊637 就是右子樹 (因為中序是左中右)

3.接著先處理左邊，中序是425 ,後序是452 ,root是2 ，左結點是4,右結點是5

4.然後再用相同的方法處理右邊,這要注邊左邊的右邊對應的index, 左半部中序跟後序一樣 右半部中序是後序的index+1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int searchNode(int inorder[], int inorderSize, int key){
    int i;
    for (i = 0; i < inorderSize; i++) {
        if (key == inorder[i]) {
            return i;
        }
    }
    return -1;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {

    if (inorder == NULL || postorder == NULL
        || inorderSize == 0 || postorderSize == 0) return NULL;

    struct TreeNode *root
        = (struct TreeNode *)malloc(sizeof(struct TreeNode));

    /* postorder 最後一個值是root */
    root->val = postorder[postorderSize - 1];

    /*去中序裡找到root 進行切割 */
    int index = searchNode(inorder, inorderSize, postorder[postorderSize - 1]);
    if (index == -1) return NULL;

    root->left = buildTree(inorder, index, postorder, index);
    root->right = buildTree(inorder + index + 1, inorderSize - index - 1,
                            postorder + index, inorderSize - index - 1);

    return root;
}

Construct Binary Tree from Preorder and Inorder Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int searchNode(int inorder[], int inorderSize, int key){
    int i;
    for (i = 0; i < inorderSize; i++) {
        if (key == inorder[i]) {
            return i;
        }
    }
    return -1;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
     if (inorder == NULL || preorder == NULL
        || inorderSize == 0 || preorderSize == 0) return NULL;

    struct TreeNode *root
        = (struct TreeNode *)malloc(sizeof(struct TreeNode));

    /* preorder 第一個值是root */
    root->val = preorder[0];

    /*去中序裡找到root 進行切割 */
    int index = searchNode(inorder, inorderSize, preorder[0]);
    if (index == -1) return NULL;



    root->left = buildTree(preorder+1, index, inorder , index);
    root->right = buildTree(preorder + index + 1, inorderSize - index - 1,
                            inorder + index + 1, inorderSize - index - 1);

    return root;
}