剑指offer_7_重建二叉树

• 2019 年 10 月 7 日
• 筆記

题目：重建二叉树

描述：

输入某二叉树的前序遍历和中序遍历的结果，请重新构建该二叉树。假设输入的前序遍历和中序遍历的结果中不包含重复的数字。例如输入的前序遍历序列为｛5，2，1，7，6，9｝和中序遍历为{1，2，5，6，7，9},则重建出二叉树并输出它的头结点。

思路：利用前序遍历根节点左右俩侧是左右子树，中序遍历第一个节点就根节点的特性，将一棵树细分成很多子树，从根节点往下构造。

Map<Integer,Integer> map = new HashMap<>();    public TreeNode fill(int[] pre,int[] in) {      for (int i = 0; i < in.length; i++) {          map.put(in[i],i);      }      return reBuild(pre,0,pre.length -1,0);  }      // pre[] 前序遍历 preL：当前前序遍历数组的最左侧 preR：当前前序遍历数组的最右侧 inL中序遍历的最左侧  public TreeNode reBuild(int[] pre,int preL,int preR,int inL) {       if (preL > preR) {           return null;       }      TreeNode root = new TreeNode(pre[preL]);       // 得到该节点的下标       int inIndex = map.get(root.value);       // 左子树的大小       int lTreeSize = inIndex - inL;       // 递归左边的子树       root.left = reBuild(pre,preL + 1,preL + lTreeSize,inL);       // 递归右边的子树 inL + lTreeSize + 1:当前中序遍历数组的最左侧元素       root.right = reBuild(pre,preL + lTreeSize + 1,preR,inL + lTreeSize + 1);      return root;   }  }    class TreeNode {      TreeNode left;      TreeNode right;      int value;      public TreeNode(int value) {          this.value = value;      }  }

利用前序后续遍历的特性，重新构建二叉树。