【二叉樹還原】已知後序和中序還原二叉樹

leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal

一、問題描述

給定樹的中序周遊和後序周遊，構造二叉樹。假定樹中不存在重複項

中序 = [9,3,15,20,7]

後序 = [9,15,7,20,3]

傳回下列二叉樹:

    3

   / \

  9  20

    /  \

   15   7

二、解題思路

二叉樹

        後序周遊：左右根  --- 9,3,15,20,7

        中序周遊：左根右 --- 9,15,7,20,3

    是以，後序周遊最後一個元素一定是根節點->在中序周遊中找該元素所在位置，則該元素左邊就是該根節點左子樹部分，右邊就是該根節點右子樹部分->再分别對這兩個部分遞歸做相同算法。

三、算法實作

/*********************************************
Author:tmw
date:2018-5-8
*********************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode;

/**在中序周遊中找根節點所在位置，傳回位置下标**/
int find_root_index( int* inorder, int inorderLeft, int inorderRight, int root_elem )
{
    if( !inorder || inorderLeft<0 || inorderLeft>inorderRight )
        return -1;
    int i;
    for( i=inorderLeft; i<=inorderRight; i++ )
        if( inorder[i] == root_elem )
            return i;
    return -1;
}

/**找到根節點**/
TreeNode* getRoot( int* inorder, int in_left, int in_right, int* postorder, int post_left, int post_right )
{
    /**參數合法性判斷**/
    if( !inorder || !postorder ) return NULL;
    if( in_left<0 || in_right<in_left ) return NULL;
    if( post_left<0 || post_right<post_left ) return NULL;

    /**通過後序找到根節點，并給它配置設定空間**/
    int rootElem = postorder[post_right];
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = rootElem;
    root->left = NULL;
    root->right = NULL;

    /**找到根節點在中序中的下标**/
    int root_index = find_root_index(inorder,in_left,in_right,rootElem);
    if( root_index == -1 ) return NULL;

    /**遞歸求左子樹**/
    root->left = getRoot(inorder,in_left,root_index-1,postorder,post_left,post_left+root_index-in_left-1);
    /**遞歸求右子樹**/
    root->right = getRoot(inorder,root_index+1,in_right,postorder,post_left+root_index-in_left,post_right-1);
    return root;
}

TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize)
{
    if( !inorder || !postorder ) return NULL;
    return getRoot(inorder,0,inorderSize-1,postorder,0,postorderSize-1);
}
           

四、執行結果

accpet

夢想還是要有的，萬一實作了呢~~~ヾ(◍°∇°◍)ﾉﾞ~~~