从中序与后序遍历序列构造二叉树

题目描述：根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）   

链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/   

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归

根据中序遍历和后序遍历的性质，通过递归的方式求解，递归的过程如下：

• 首先，如果中序遍历序列或后序遍历序列为空，直接返回空树；

• 因为后序遍历序列的最后一个值为根节点，所以首先根据这个初始化得到当前的根节点root；

• 然后根据根节点root在中序遍历序列中的位置，根节点前面的值都是当前根节点的左子树节点，得到当前根节点左右子树节点的数量；

• 然后通过调用递归方法得到当前根节点的左右子树；

• 最后返回root即为还原后的树。

【每日寄语】 命运负责洗牌，但是玩牌的是我们自己！