基础版本

image.png

image.png
image.png

下标换算用具体例子来算
image.png

注意要判断越界情况, 因为如果根节点没有左树的话
image.png
比如这个，前序2、3、4
中序2、3、4
findIndex = L2
那么L1 + findIndex - L2 = L1
而左边界是L1+1了，就无效范围了
image.png

  1.  public TreeNode buildTree(int[] preorder, int[] inorder) {
  2.         return f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
  3.     }
  5.     public  TreeNode f(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
  6.         if (L1 > R1) {
  7.             return null;
  8.         }
  9.         if (L1 == R1) {
  10.             return new TreeNode(pre[L1]);
  11.         }
  12.         TreeNode head = new TreeNode(pre[L1]);
  13.         int findIndex = 0;
  14.         for (; findIndex < R2; findIndex++) {
  15.             if (in[findIndex] == pre[L1]) {
  16.                 break;
  17.             }
  18.         }
  19.         head.left = f(pre, L1 + 1, L1 + findIndex - L2, in, L2, findIndex - 1);
  20.         head.right = f(pre, L1 + findIndex - L2 + 1, R1, in, findIndex + 1, R2);
  21.         return head;
  22.     }

优化版本

上面那个for循环是可以用一张map代替掉的， 记录in中每个值出现的位置

  1. public TreeNode buildTree2(int[] preorder, int[] inorder) {
  2.         HashMap<Integer, Integer> map = new HashMap<>();
  3.         for (int i = 0; i < inorder.length; i++) {
  4.             map.put(inorder[i], i);
  5.         }
  6.         return f2(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
  7.     }
  9.     public  TreeNode f2(int[] pre, int L1, int R1, int[] in, int L2, int R2, HashMap<Integer, Integer> map) {
  10.         if (L1 > R1) {
  11.             return null;
  12.         }
  13.         if (L1 == R1) {
  14.             return new TreeNode(pre[L1]);
  15.         }
  16.         TreeNode head = new TreeNode(pre[L1]);
  17.         int findIndex = map.get(pre[L1]);
  18.         head.left = f2(pre, L1 + 1, L1 + findIndex - L2, in, L2, findIndex - 1, map);
  19.         head.right = f2(pre, L1 + findIndex - L2 + 1, R1, in, findIndex + 1, R2, map);
  20.         return head;
  21.     }

时间复杂度O(N)

因为找头现在是O(1)的，然后每调一次f函数搞定一个头，所以总的就是O(N)