（17）根据前序遍历和中序遍历重构二叉树

摘自剑指offer面试题7

一、描述

• 给定两个数组 inOrder, preOrder，
• inOrder代表前序遍历二叉树结点的输出
• preOrder代表中序遍历二叉树结点的输出
• 结点的值不重复。

请重构二叉树

 

二、思路

• 前序遍历的输出顺序是根，左，右
• 中序遍历结点的输出是左、根、右
• 顺便复习一下后序遍历结点的输出是左、右、根
• 根据前序遍历的第一个结点找中序遍历中结点的位置
• 中序遍历数组左边的都是根结点的左孩子
• 中序遍历数组右边的都是根结点的右孩子
• 根据中序遍历的左右子树，可以将前序遍历再划分成两个左右子数组
• 递归重复上述步骤，直到左右子数组数目为0。
• 画个图思路会清晰很多，请自己画一下

 

三、Code

 1 package algorithm; 2  3 import java.util.HashSet; 4  5 /** 6  * Created by adrian.wu on 2019/3/22. 7  */ 8 public class ReconstructBinaryTree { 9     public static class BinaryTree {10         int val;11         BinaryTree left;12         BinaryTree right;13 14         public BinaryTree(int val) {15             this.val = val;16             left = null;17             right = null;18         }19     }20     21     public static BinaryTree construct(int[] preOrder, int[] inOrder) {22         int n;23         if ((n = preOrder.length) == 0) return null;24 25         int headVal = preOrder[0];26         int end = 0;27         while (end < inOrder.length && inOrder[end] != headVal) end  ;28 29         int[] il = new int[end], ir = new int[n - end - 1], pl = new int[end], pr = new int[n - end - 1];30 31         HashSet<Integer> ilSet = new HashSet<>();32         for (int i = 0; i < end; i  ) {33             il[i] = inOrder[i];34             ilSet.add(il[i]);35         }36 37         for (int i = end   1; i < n; i  ) ir[i-end-1] = inOrder[i];38 39         int l = 0, r = 0;40         for(int i = 0; i < n; i  ){41             int val = preOrder[i];42             if(ilSet.contains(val)) pl[l  ] =val;43             else if(val != headVal) pr[r  ] =val;44         }45 46         BinaryTree head = new BinaryTree(headVal);47         head.left = construct(pl, il);48         head.right = construct(pr, ir);49         return head;50     }51 52     public static void preOrderPrint(BinaryTree head) {53         if(head == null) return;54 55         System.out.println(head.val);56         preOrderPrint(head.left);57         preOrderPrint(head.right);58     }59 60     public static void main(String[] args) {61         int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};62         int[] in = {4, 7, 2, 1, 5, 3, 8, 6};63 64         BinaryTree head = construct(pre, in);65         preOrderPrint(head);66     }67 68 }

 

来源：http://www.icode9.com/content-4-145851.html