题解 | #牛群的树形结构重建#

题目考察的知识点 : 中序遍历和后序遍历构造二叉树

题目解答方法的文字分析：

后序遍历的最后一个元素为整棵树的根节点

在中序遍历中找到根节点的位置，左边为左子树的中序遍历，右边为右子树的中序遍历；

根据左子树的中序遍历长度，确定后序遍历中左右子树的分界点；

递归地构造左右子树，返回根节点。

本题解析所用的编程语言: java

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param inOrder int整型一维数组
     * @param postOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode buildTree (int[] inOrder, int[] postOrder) {
        // write code here
        int n = inOrder.length;
        return build(inOrder, postOrder, 0, n - 1, 0, n - 1);
    }

    private TreeNode build(int[] inOrder, int[] postOrder, int left, int right,int start, int end) {
        if (left > right || start > end) {
            return null;
        }
        int val = postOrder[end];
        TreeNode root = new TreeNode(val);
        int len = 0;
        for (int i = left; i <= right && inOrder[i] != val; i++,len++);
        root.left = build(inOrder, postOrder, left, left + len - 1, start, start + len - 1);
        root.right = build(inOrder, postOrder, left + len + 1, right, start + len, end - 1);
        return root;
    }
}