剑指Offer07~ 由前序和中序遍历重建二叉树

妖狐艹你老母 2022-05-13 09:18 165阅读 0赞

## 题目描述 ##

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历结果中都不含重复的数字。例如输入前序遍历序列｛1,2,4,7,3,5,6,8｝和中序遍历序列｛4,7,2,1,5,3,8,6｝，则重建出如图所示的二叉树并输出它的头结点。  
![这里写图片描述][SouthEast]

### 思路分析 ###

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部  
分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。  
步骤大致为：

1、前序序列第一个节点是该二叉树的根节点，得到它root（值为1）；  
2、根据第1步得到的结点（1），在中序序列中找到其所在位置并记录下标索引inIndex（索引为3），由图可以看出，该结点将中序序列分为两个部分，分别对应该二叉树的左子树和右子树，得到root结点的左子树结点个数leftTreeSize；  
3、递归创建root的左子树；  
4、递归创建root的右子树。  
![这里写图片描述][Center]

### 代码实现 ###

说明：我先将各部分关键代码分别罗列出来，最后将会是完整代码。

#### 首先构建二叉树结构（部分代码） ####

class TreeNode { 
        int val;// 节点数据
        TreeNode left;// 左孩子
        TreeNode right;// 右孩子
        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

#### 缓存中序序列—方便查找索引下标（部分代码） ####

// 缓存中序遍历数组的每个值对应的索引
        // 9 0
        // 3 1
        // 15 2
        // 20 3
        // 7 4
        private static Map<Integer, Integer> inOrderNumsIndexs = new HashMap<Integer, Integer>();
    
        /** * * @param pre前序遍历数组[3,9,20,15,7] * @param in中序遍历数组[9,3,15,20,7] * @return */
        public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            for (int i = 0; i < in.length; i++)
                inOrderNumsIndexs.put(in[i], i);
            // pre前[3,9,20,15,7],前序开始位置0，前序结束位置4，in中[9,3,15,20,7]，中序开始位置0，中序结束位置4
            return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        }

#### 递归函数—关键、关键、关键。。。（部分代码） ####

/** * * @param pre前序遍历数组[3,9,20,15,7] * @param preL前序序列开始的位置 * @param preR前序序列结束的位置 * @param in中序遍历数组[9,3,15,20,7] * @param inL中序序列开始的位置 * @param inR中序序列结束的位置 * @return */
        private static TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
            if (preL > preR)
                return null;
            // 创建一个节点 pre[preL]
            TreeNode root = new TreeNode(pre[preL]);
            // 得到 pre[preL]在中序序列中的索引下标
            int inIndex = inOrderNumsIndexs.get(root.val);
            // 从中序序列中获取某节点的左子树的节点个数
            int leftTreeSize = inIndex - inL;
            // 前序序列结束的位置
            int leftPreOrderEndIndex = preL + leftTreeSize;
            // 递归创建左子树
            root.left = reConstructBinaryTree(pre, preL + 1, leftPreOrderEndIndex, in, inL, inL + leftTreeSize - 1);
            // 递归创建右子树
            root.right = reConstructBinaryTree(pre, leftPreOrderEndIndex + 1, preR, in, inL + leftTreeSize + 1, inR);
            return root;
        }

#### 完整代码来了~~copy可用 ####

package com.tree;
    
    import java.util.HashMap;
    import java.util.Map;
    
    public class Test { 
        // 缓存中序遍历数组的每个值对应的索引
        // 9 0
        // 3 1
        // 15 2
        // 20 3
        // 7 4
        private static Map<Integer, Integer> inOrderNumsIndexs = new HashMap<Integer, Integer>();
    
        /** * * @param pre前序遍历数组[3,9,20,15,7] * @param in中序遍历数组[9,3,15,20,7] * @return */
        public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            for (int i = 0; i < in.length; i++)
                inOrderNumsIndexs.put(in[i], i);
            // pre前[3,9,20,15,7],前序开始位置0，前序结束位置4，in中[9,3,15,20,7]，中序开始位置0，中序结束位置4
            return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        }
    
        /** * * @param pre前序遍历数组[3,9,20,15,7] * @param preL前序序列开始的位置 * @param preR前序序列结束的位置 * @param in中序遍历数组[9,3,15,20,7] * @param inL中序序列开始的位置 * @param inR中序序列结束的位置 * @return */
        private static TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
            if (preL > preR)
                return null;
            // 创建一个节点 pre[preL]
            TreeNode root = new TreeNode(pre[preL]);
            // 得到 pre[preL]在中序序列中的索引下标
            int inIndex = inOrderNumsIndexs.get(root.val);
            // 从中序序列中获取某节点的左子树的节点个数
            int leftTreeSize = inIndex - inL;
            // 前序序列结束的位置
            int leftPreOrderEndIndex = preL + leftTreeSize;
            // 递归创建左子树
            root.left = reConstructBinaryTree(pre, preL + 1, leftPreOrderEndIndex, in, inL, inL + leftTreeSize - 1);
            // 递归创建右子树
            root.right = reConstructBinaryTree(pre, leftPreOrderEndIndex + 1, preR, in, inL + leftTreeSize + 1, inR);
            return root;
        }
    
        /** * 先序遍历 * * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 * * @param node * 遍历的节点 */
        public static void preOrderTraverse(TreeNode node) {
            if (node == null)
                return;
            System.out.print(node.val + " ");
            preOrderTraverse(node.left);
            preOrderTraverse(node.right);
        }
    
        /** * 中序遍历 * * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 * * @param node * 遍历的节点 */
        public static void inOrderTraverse(TreeNode node) {
            if (node == null)
                return;
            inOrderTraverse(node.left);
            System.out.print(node.val + " ");
            inOrderTraverse(node.right);
        }
    
        // 测试
        public static void main(String[] args) {
    
            // int[] preOrder={1,2,4,7,3,5,6,8};
            // int[] inOrder={4,7,2,1,5,3,8,6};
            int[] preOrder = { 3, 9, 20, 15, 7 };
            int[] inOrder = { 9, 3, 15, 20, 7 };
            System.out.print("输入前序序列：");
            for (int i = 0; i < preOrder.length; i++) {
                System.out.print(preOrder[i] + " ");
            }
            System.out.print("\n输入中序序列：");
            for (int i = 0; i < inOrder.length; i++) {
                System.out.print(inOrder[i] + " ");
            }
            TreeNode node = reConstructBinaryTree(preOrder, inOrder);
            System.out.println("\n输出构建后的前序遍历结果：");
            preOrderTraverse(node);
            System.out.println("\n输出构建后的中序遍历结果：");
            inOrderTraverse(node);
        }
    }
    
    class TreeNode {
    
        int val;// 节点数据
        TreeNode left;// 左孩子
        TreeNode right;// 右孩子
    
        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
    
        }
    }

[SouthEast]: /images/20220513/c8d2cff25c8343e6a6f9b58929a4eb6b.png
[Center]: /images/20220513/0a6dd465ac8944718f5dffba04e61237.png