剑指offer刷题记—第7题_重建二叉树

谁借莪１个温暖的怀抱￠ 2021-09-23 09:42 280阅读 0赞

### 题目： ###

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路就是：遇到二叉树就可以向递归方向进行思考。前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果

**
     * @program: suanfa
     * @description: 重新创建二叉树
     * @author: zi jian
     * @create: 2019-10-22 08:59
     * 题目描述：
     * 输入某二叉树的前序遍历和中序遍历的结果，请重新构造出该二叉树。
     * 假设输入的前序遍历和中序遍历的结果中不包含重复的数字。
     * 例如输入的前序遍历序列为｛1，2，4，7，3，5，6，8｝和中序遍历为｛4，7，2，1，5，3，6，8｝，
     * 则重建出二叉树并输出它的头结点
     */
    public class RebuildBinaryTree {
        private Map<Integer, Integer> inOrderMap = new HashMap<>();
    
        /**
         * 根据前序和中序遍历序列完成二叉树的重建
         *
         * @param preOrder 前序遍历序列
         */
        public TreeBNode reconstructe(int[] preOrder, int pStartIndex, int pEndIndex, int inOrderL) {
    
            if (pStartIndex > pEndIndex)
                return null;
            //当前节点也相当于前序中的第一个
            TreeBNode root = new TreeBNode(preOrder[pStartIndex]);
            //获取中序遍历的下标位置
            int inIndex = inOrderMap.get(preOrder[pStartIndex]);
            //根据中序遍历看左子树的长度
            int LeftTreeSize = inIndex - inOrderL;
            //左子树
            root.left = reconstructe(preOrder, pStartIndex + 1, pStartIndex + LeftTreeSize, inOrderL);
            //右子树
            root.right = reconstructe(preOrder, pStartIndex + LeftTreeSize + 1, pEndIndex, inOrderL + LeftTreeSize + 1);
            return root;
        }
    
        public void putHashmap(int[] inOrder) {
            for (int i = 0; i < inOrder.length; i++) {
                inOrderMap.put(inOrder[i], i);
            }
        }