【二叉树还原】已知后序和中序还原二叉树

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

梦想还是要有的，万一实现了呢~~~ヾ(◍°∇°◍)ﾉﾞ~~~