本文共 2528 字，大约阅读时间需要 8 分钟。

链接：

大意：

给定二叉树的前序遍历pre和中序遍历in（pre和in都是整型数组），构造该二叉树。例子：

思路：

每一颗树（或子树），前序遍历的第一个节点为根节点，找到根节点在中序遍历的位置（记为s吧），则在中序遍历中，s左边的元素都是根节点的左子树，s右边的元素都是根节点的右子树。

即记当前树的先序遍历序列在pre中的范围是[s1,e1]，中序遍历序列在in中的范围是[s2,e2]。则对于找到的树（根节点值肯定是pre[s1]，由于先序遍历的第一个值为根节点），s为pre[s1]在in中的位置，则根节点左子树在pre的范围是[s1 + 1, s1+ 1 + s - s1]，根节点左子树在in中的范围是[s2, s - 1]；根节点右子树在pre中的范围是[s1 + 1 + s - s1 + 1, e1]，根节点右子树在in中的范围是[s + 1, e2]

之后便是递归构造树。

代码：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode buildTree(int[] pre, int[] in) {        if (pre.length == 0)            return null;        TreeNode root = buildTree(pre, 0, pre.length - 1, in, 0, in.length - 1);        return root;    }    public TreeNode buildTree(int[] pre, int s1, int e1, int[] in, int s2, int e2) {        if (s1 > e1)            return null;        // 找到当前根节点在in中的位置        TreeNode root = new TreeNode(pre[s1]);        int s = s2, count = 0; // s记录根节点在in中的位置  count记录根的左子树有多少个节点        while (s <= e2) {            if (in[s] == pre[s1])                break;            s++;            count++;        }        root.left = buildTree(pre, s1 + 1, s1 + count, in, s2, s - 1);        root.right = buildTree(pre, s1 + count + 1, e1, in, s + 1, e2);        return root;    }}

结果：

结论：

提交之前，我还是很相信这个方法的胜率的....  奈何事实在眼前，CAI（稍后优化） 

改进：

思考了一下，耗时较多的应该是在in中查找根节点的位置，是一个O（n）的操作。由于题目规定了每个节点的值都是不同的，于是可以使用一个map存储in中各个值与其在in中对应位置的映射，这时查找根节点在in中的时间复杂度变为O（1）了。改进代码如下：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode buildTree(int[] pre, int[] in) {        if (pre.length == 0)            return null;        Map
   
     map = new HashMap<>();        for (int i = 0; i < in.length;i++) {            map.put(in[i], i);        }        TreeNode root = buildTree(pre, 0, pre.length - 1, in, 0, in.length - 1, map);        return root;    }    public TreeNode buildTree(int[] pre, int s1, int e1, int[] in, int s2, int e2, Map
    
      map) {        if (s1 > e1)            return null;        // 找到当前根节点在in中的位置        TreeNode root = new TreeNode(pre[s1]);        int s = map.get(pre[s1]), count = s - s2; //s记录根节点在in中的位置  count记录根的左子树有多少个节点        root.left = buildTree(pre, s1 + 1, s1 + count, in, s2, s - 1, map);        root.right = buildTree(pre, s1 + count + 1, e1, in, s + 1, e2, map);        return root;    }}
    
   

转载地址：http://htesi.baihongyu.com/