"Coding Interview Guide" -- 先序、中序和后序数组两两结合重构二叉树

【题目】

　　已知一棵二叉树的所有节点值都不同，给定这棵二叉树正确的先序、中序和后序数组。要求分别实现任意两种数组结合重构原来的二叉树，并返回重构二叉树的头节点

先序 + 中序 ==> 二叉树

　　import java.util.HashMap;

 1 public Node preInToTree(int[] pre, int[] in)
 2 {
 3     if(pre == null || in == null)
 4     {
 5         return null;
 6     }
 7 
 8     HashMap<Integer, Integer> map = new HashMap<>();        // 哈希表的键值对用于记录元素及其索引
 9     for(int i = 0; i < in.length; i++)
10     {
11         map.put(in[i], i);
12     }
13         
14     return preIn(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
15 }
16 
17 public Node preIn(int[] p, int pi, int pj, int[] n, int ni, int nj, HashMap<Integer, Integer> map)
18 {
19     if(pi > pj)
20     {
21         return null;
22     }
23 
24     Node head = new Node(p[pi]);            // 当前先序数组的第一个元素是当前子树的头节点
25     int index = map.get(p[pi]);
26     head.left = preIn(p, pi + 1, pi + index - ni, n, ni, index - 1, map);
27     head.right = preIn(p, pi + index - ni + 1, pj, n, index + 1, nj, map);
28     return head;
29 }

中序 + 后序 ==> 二叉树

 1 public Node inPosToTree(int[] in, int[] pos)
 2 {
 3     if(in == null || pos == null)
 4     {
 5         return null;
 6     }
 7 
 8     HashMap<Integer, Integer> map = new HashMap<>();             // 哈希表的键值对用于记录元素及其索引
 9     for(int i = 0; i < in.length; i++)
10     {
11         map.put(in[i], i);
12     }
13 
14     return inPos(in, 0, in.length - 1, pos, 0, pos.length - 1, map);
15 }
16 
17 public Node inPos(int[] n, int ni, int nj, int[] s, int si, int sj, HashMap<Integer, Integer> map)
18 {
19     if(si > sj)
20     {
21         return null;
22     }
23 
24     Node head = new Node(s[sj]);           // 当前后序数组的最后一个元素是当前子树的头节点
25     int index = map.get(s[sj]);
26     head.left = inPos(n, ni, index - 1, s, si, si + index - ni - 1, map);
27     head.right = inPos(n, index + 1, nj, s, si + index - ni, sj - 1, map);
28     return head;
29 }

先序 + 后序 ==> 二叉树

　　在大多数情况下是无法通过先序数组和后序数组重建二叉树的，因为很多结构不同的树的先序数组和后序数组相同

　　只有当一棵二叉树满足除叶节点外，其它所有节点都有左孩子和右孩子时，才可以被先序和后序数组重建出来

 1     public Node prePosToTree(int[] pre, int[] pos)
 2     {
 3         if(pre == null || pos == null)
 4         {
 5             return null;
 6         }
 7 
 8         HashMap<Integer, Integer> map = new HashMap<>();
 9         for(int i = 0; i < pos.length; i++)
10         {
11             map.put(pos[i], i);
12         }
13 
14         return prePos(pre, 0, pre.length - 1, pos, 0, pos.length - 1, map);
15     }
16 
17     public Node prePos(int[] p, int pi, int pj, int s, int si, int sj, HashMap<Integer, Integer> map)
18     {
19         Node head = new Node(s[sj--]);
20         if(pi == pj)
21         {
22             return head;
23         }
24         int index = map.get(p[++pi]);
25         head.left = prePos(p, pi, pi + index - si, s, si, index, map);
26         head.right = prePos(p, pi + index - si + 1, pj, s, index + 1, sj, map);
27         return head;
28     }

来源：左程云老师《程序员代码面试指南》