4.重建二叉树

题目描述

给出一个二叉树的先序和中序遍历,还原这棵二叉树

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   /**
     * 重建二叉树
     *
     * @param pre
     * @param in
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }
    /**
     *            5
     *         /    \
     *        3      2
     *       / \    / \
     *      1  4    6  8
     *    pre[根左右]:5 3 1 4 2 6 8
     *    in[左根右] :1 3 4 5 6 2 8
     *    out[左右根]:1 4 3 6 8 2 5
     * @param pre
     * @param preL
     * @param preR
     * @param in
     * @param inL
     * @param inR
     * @return
     */
    private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preL]);
        int i = inL;
        while (in[i] != pre[preL] && i <= inR) {
            ++i;
        }
        /**
         *      *            5
         *      *         /    \
         *      *        3      2
         *      *       / \    / \
         *      *      1  4    6  8
         *      *    pre[根左右]:5 3 1 4 2 6 8
         *      *    in [左根右]:1 3 4 5 6 2 8
         *      *    out[左右根]:1 4 3 6 8 2 5
         */
        root.left = reConstructBinaryTree(pre, preL + 1, preL + (i - inL), in, inL, i - 1);
        root.right = reConstructBinaryTree(pre, preL + (i - inL) + 1, preR, in, i + 1, inR);
        return root;
    }
}