今天做了一道由前序遍历和后序遍历得到二叉树的题目，回想起自己好早以前做的两道类似的题目，发现方法都差不多，故这里做一个整理。

题目描述:
给定一棵有n个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。
若某节点只有一个子结点，则此处将其看作左儿子结点

样例

5,[3,2,1,4,5],[1,5,4,2,3]

图示:

解题思路:
首先我们清楚， 根据前序遍历和后序遍历是得不到一棵唯一的二叉树的，但是由于题目中有若某节点只有一个子结点，则此处将其看作左儿子结点这个限制，故这里得到的二叉树就是唯一的了，那么对于这类构造题，我们一般都要使用递归的思想来解决，使用递归函数的参数有[al, ar], [bl, br]，表示通过第一个序列的[al, ar]和第二个序列的[bl, br]构造一棵二叉树，分析到这里，我们只需要宏观的考虑对于当前的根节点它的左子树和右子树的区间是多少就ok了，这里由于题目中的例子没有右子树，所以这里我们用前序为[1, 2, 3, 4, 5, 6, 7],后序为[3, 4, 2, 6, 7, 5, 1]的这颗二叉树来分析, 具体分析如下：

考虑到这里之后，递归函数的写法也就明确了，这题也就解出来了。

参考代码:

import java.util.*;

class TreeNode{
    int val;
    TreeNode l, r;

    public TreeNode(int val) {
        this.val = val;
        this.l = null;
        this.r = null;
    }
}

public class Solution {
    /**
     * 返回所求中序序列
     * @param n int整型 二叉树节点数量
     * @param pre int整型一维数组 前序序列
     * @param suf int整型一维数组 后序序列
     * @return int整型一维数组
     */
    int[] path;
    int u;
    TreeNode construct(int n, int preL, int preR, int sufL, int sufR, int[] pre, int[] suf) {
        if(preL > preR || sufL > sufR) return null;
        if(preL == preR) {
            path[u ++] = pre[preL];
            return new TreeNode(pre[preL]);
        }

        TreeNode root = new TreeNode(pre[preL]); // 获取根节点

        int lv = pre[preL + 1];
        int idx = -1;
        for(int i=0; i<n; i++) {
            if(suf[i] == lv) {
                idx = i;
                break;
            }
        }

        root.l = construct(n, preL+1, preL+idx-sufL+1, sufL, idx, pre, suf);
        path[u ++] = root.val;
        root.r = construct(n, preL+idx-sufL+2, preR, idx+1, sufR-1, pre, suf);

        return root;
    }

    public int[] solve (int n, int[] pre, int[] suf) {
        // write code here
        path = new int[n];
        u = 0;
        TreeNode root = construct(n, 0, n-1, 0, n-1, pre, suf);

        return path;
    }
}

另外的两道类似的题目:
从前序与中序遍历序列构造二叉树
从中序与后序遍历序列构造二叉树

这里对这类题目的做法做一个小总结:

1. 确定找根节点的那个序列
2. 在另一个序列中找到当前要找节点的左右子树所对应的区间
3. 在寻找根节点的序列中通过另一个序列的划分也对该序列的左右子树所对应的区间做一个划分

完成了这三步，递归函数也就可以写出来了