题解 | #重建二叉树#

<非递归实现>
看题解里千篇一律的递归实现，与大家分享新的非递归方法，仅为扩展思路。

• 主要思路：

1. 遍历前序序列pre的每一个值，对每个值，创建节点，查找其在中序序列in中的索引位置，判断该位置为前方节点中序序列in的左子树还是右子树（见详解），将该节点接到前方节点对应的left或right上。
2. 记录当前节点的左子树数组在中序序列in中索引，和右子树数组在中序序列in中的起止索引。
3. 如果起止索引值一致，则子树为null。
4. 最后，返回根节点。

• 核心方法：
  用数组记录子树的起止索引
• 详解
  用例：前序{1,2,4,7,3,5,6,8} 中序{4,7,2,1,5,3,8,6}
  图片是我的推导过程，主要看左边的数字部分。
  

1. 需要的变量
   遍历pre的i
   记录in左子树起止的数组（含左不含右）
   记录in右子树起止的数组（含左不含右）

2. 流程
   先看图片中的吧，等我有时间了再敲出来

3. 代码

   /**
   * Definition for binary tree
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode(int x) { val = x; }
   * }
   */
   public class Solution {
     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
         if(pre == null || in == null|| pre.length == 0 || in.length == 0) return null;
         TreeNode [] nodeArray = new TreeNode[pre.length];//记录节点
         int[][] idxLeftTreeIn = new int[in.length][2];//In的左子树起止索引（含左不含右）
         int[][] idxRightTreeIn = new int[in.length][2];//In的右子树起止索引
   
         //创建根节点
         int curNodeValue0 = pre[0];
         TreeNode curNode0 = new TreeNode(curNodeValue0);
         nodeArray[0] = curNode0;
         int idxRootIn0 = 0;
         for(idxRootIn0 = 0; idxRootIn0 < in.length;++idxRootIn0){
             if(in[idxRootIn0] == curNodeValue0) break;
         }
         //记录左右子树的in起止
         idxLeftTreeIn[0][0] = 0;
         idxLeftTreeIn[0][1] = idxRootIn0;//不含右，所以记录到根节点
         idxRightTreeIn[0][0] = idxRootIn0+1;
         idxRightTreeIn[0][1] = in.length;
   
         //遍历前序数组中剩余的每个节点
         for(int idxPre = 1; idxPre<pre.length;++idxPre){
   
             //idxPre:当前节点
             //取出Pre中的节点，建立树节点，保存
             int curNodeValue = pre[idxPre];
             TreeNode curNode = new TreeNode(curNodeValue);
             nodeArray[idxPre] = curNode;
             //获得其在in数组中的位置索引
             int idxRootIn = 0;
             for(idxRootIn = 0; idxRootIn < in.length;++idxRootIn){
                 if(in[idxRootIn] == curNodeValue) break;
             }
             //倒序遍历前面的节点，判断当前节点是在前面节点的in左子树还是右子树中
             int idxChildTreeLeftIn=0,idxChildTreeRightIn = 0;//记录所属子树的范围
             for(int idxIn = (idxPre-1);idxIn>=0;--idxIn){
                 //判断是否是前序节点的左子树中的节点
                 if(idxLeftTreeIn[idxIn][0]<=idxRootIn && idxRootIn < idxLeftTreeIn[idxIn][1]){
                     //在该前序节点的左子树中
                     nodeArray[idxIn].left = curNode;
                     //记录前序节点左子树范围
                     idxChildTreeLeftIn = idxLeftTreeIn[idxIn][0];
                     idxChildTreeRightIn = idxLeftTreeIn[idxIn][1];
                     break;
                 }
                 //判断是否是前序节点的右子树中的节点
                 else if(idxRightTreeIn[idxIn][0] <=idxRootIn && idxRootIn < idxRightTreeIn[idxIn][1]){
                     nodeArray[idxIn].right = curNode;
                     //记录前序节点右子树范围
                     idxChildTreeLeftIn = idxRightTreeIn[idxIn][0];
                     idxChildTreeRightIn = idxRightTreeIn[idxIn][1];
                     break;
                 }
             }
             //记录当前节点curNode的左右子树的in起止索引
             idxLeftTreeIn[idxPre][0] = idxChildTreeLeftIn;
             idxLeftTreeIn[idxPre][1] = idxRootIn;
             if(idxLeftTreeIn[idxPre][0] == idxLeftTreeIn[idxPre][1]){
                 //子数组左右边界一样，说明左子树没有节点了
                 curNode.left = null;
             }
             idxRightTreeIn[idxPre][0] = idxRootIn+1;
             idxRightTreeIn[idxPre][1] = idxChildTreeRightIn;
             if(idxRightTreeIn[idxPre][0] == idxRightTreeIn[idxPre][1]){
                 curNode.right = null;
             }
         }
   
         return nodeArray[0];
     }
   }