摘自剑指offer面试题7 一、描述
请重构二叉树
二、思路
三、Code1 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./content-4-145851.html |
|