【剑指offer】重建二叉树

前序序列{1,2,4,7,3,5,6,8} 根->左->右
中序序列{4,7,2,1,5,3,8,6} 左->根->右

1. 前序序列的第一个数字是1，说明根节点是1。
2. 在中序序列中找到数字1的位置mid，mid左边为左子树的中序序列{4,7,2}，右边为右子树的中序序列{5,3,8,6}。
3. 由于知道左右子树的个数，则前序序列中左子树序列为{2,4,7}，右子树序列为{3,5,6,8}。

思路很清晰，是一个递归的过程。写不写的出来，全靠基本功了。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode dfs(int[] pre, int[] in, int preL, int preR, int inL, int inR) {

        if (preL > preR || inL > inR) { // 无左子树或右子树
            return null;
        }
        int val = pre[preL]; // 前序遍历序列中的第一个数即为根节点
        TreeNode tree = new TreeNode(val);

        int mid = 0; // 找到根节点在中序遍历中的位置
        for (int i = inL; i <= inR; i++) {
            if (in[i] == val) {
                mid = i;
                break;
            }
        }

        // 在中序遍历中，根节点把序列分为左右子树
        int leftCount = mid - inL;  // 左子树节点个数
        int rightCount = inR - mid; // 右子树节点个数

        // 分别递归构造左右子树
        tree.left = dfs(pre, in, preL + 1, preL + leftCount, inL, mid - 1);
        tree.right = dfs(pre, in, preR - rightCount + 1, preR, mid + 1, inR);

        return tree;
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        int lenPre = pre.length;
        int lenIn = in.length;
        if (lenPre == 0) {
            return null;
        }

        return dfs(pre, in, 0, lenPre - 1, 0, lenIn - 1);
    }
}

调用了一个函数Arrays.copyOfRange()，使代码简洁了不少。

import java.util.Arrays;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode tree = new TreeNode(pre[0]);

        int mid = 0;
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                mid = i;
                break;
            }
        }
        tree.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,mid+1),Arrays.copyOfRange(in,0,mid));
        tree.right = reConstructBinaryTree(Arrays.copyOfRange(pre,mid+1,pre.length),Arrays.copyOfRange(in,mid+1,in.length));
        return tree;
    }
}