Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

 

这个题目是给你一棵树的中序遍历和后序遍历，让你将这棵树表示出来。其中可以假设在树中没有重复的元素。

当做完这个题之后，建议去做做第105题，跟这道题类似。

 

分析：这个解法的基本思想是：我们有两个数组，分别是IN和POST.后序遍历暗示POSR[end](也就是POST数组的最后一个元素）是根节点。之后我们可以在IN中寻找POST[END].假设我们找到了IN[5].现在我们就能够知道IN[5]是根节点，然后IN[0]到IN[4]是左子树，IN[6]到最后是右子树。然后我们可以通过递归的方式处理这个数组。

代码如下，其中改代码击败了100%的C#提交者：

/** * Definition for a binary tree node. * public class TreeNode { *     public int val; *     public TreeNode left; *     public TreeNode right; *     public TreeNode(int x) { val = x; } * } */public class Solution {    public TreeNode BuildTree(int[] inorder, int[] postorder) {        return binaryTree(postorder.Length-1,0,inorder.Length-1,inorder,postorder);    }                    public TreeNode binaryTree(int postEnd,int inStart,int inEnd,int[] inorder, int[] postorder)    {        if(postEnd<0||inStart>inEnd)           return null;                        int inindex=0;        TreeNode root=new TreeNode(postorder[postEnd]);                for(int i=inStart;i<=inEnd;i++)        {            if(inorder[i]==postorder[postEnd])            {                inindex=i;                break;            }        }                        root.left=binaryTree(postEnd-(inEnd-inindex)-1,inStart,inindex-1,inorder,postorder);        root.right=binaryTree(postEnd-1,inindex+1,inEnd,inorder,postorder);                return root;            }}

最最关键的是确定函数的实参的时候，一定不能弄错。 

root.left=binaryTree(postEnd-(inEnd-inindex)-1,inStart,inindex-1,inorder,postorder);

中的inEnd-inindex代表了右子树的元素数，为了求得左子树的最后一位，应该将该元素减去。