【剑指offer】面试题7：重建二叉树

秒速五厘米 2022-04-01 14:42 137阅读 0赞

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

在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但在中序遍历中，根节点的值在序列的中间，左子树节点的值位于根节点的左边，而右子树节点的值位于根节点的右边。因此，只要我们只需要在中序遍历的结果中查找到根节点的位置，就可以确定了根节点的左子树和右子树了，然后再递归的构建左、右子树。

![20181231110905699.png][]

下面我们就用代码实现用前序遍历和中序遍历重新构建一棵二叉树的过程：

先创建一棵二叉树：

/**
     * 构建一棵二叉树 
     */
    public class BinaryTree {
    
    	public int value;              // 当前节点的值
    	public BinaryTree leftNode;    // 当前节点的左子节点
    	public BinaryTree rightNode;   // 当前节点的右子节点
    	
    	public BinaryTree(){
    		
    	}
    	
    	public BinaryTree(int vaule){
    		this.value = value;
    		this.leftNode = null;      // 刚创建时，左右子树都为空
    		this.rightNode = null;
    	}
    }

重建二叉树：

public class ReConstructBinaryTree {
    
    	/**
    	 * @param preOrder ：前序遍历数组
    	 * @param inOrder ：中序遍历数组
    	 * @param length ： 数组长度
    	 * @return ： 根节点
    	 */
    	public static BinaryTree reConstruct(int[] preOrder, int[] inOrder, int length){
    		
    		if(preOrder == null || inOrder == null || length <= 0){
    			return null;
    		}
    		
    		return constructCore(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length -1);
    		
    	}
    
    	/**
    	 * @param preOrder ：前序遍历序列
    	 * @param startPreIndex ：前序遍历开始位置
    	 * @param endPreIndex ：前序遍历结束位置
    	 * @param inOrder ：中序遍历序列
    	 * @param startInIndex ： 中序遍历开始位置
    	 * @param endInIndex ： 中序遍历结束位置
    	 * @return 根节点
    	 */
    	private static BinaryTree constructCore(int[] preOrder, int startPreIndex, 
    			int endPreIndex, int[] inOrder, int startInIndex, int endInIndex) {
    
    		// 前序遍历数组中的第一个元素即是根节点的值
    		int rootVal = preOrder[startPreIndex];
    		// 重构二叉树
    		BinaryTree root = new BinaryTree(rootVal);
    		
    		// 只有一个根节点元素时
    		if(startPreIndex == endPreIndex){
    			if(startInIndex == endInIndex && preOrder[startPreIndex] == inOrder[startInIndex]){
    				return root;
    			}else{
    				throw new IllegalArgumentException("输入的参数有误");
    			}
    		}
    		
    		// 遍历中序遍历数组，找到根节点的位置
    		int rootInIndex = startInIndex;   // 从头开始遍历,确定根节点在中序遍历中的下标：rootInIndex
    		while(rootInIndex <= endInIndex && inOrder[rootInIndex] != rootVal){
    			++rootInIndex;
    		}
    		
    		if(rootInIndex == endInIndex && inOrder[rootInIndex] != rootVal){
    			throw new IllegalArgumentException("输入的参数有误");
    		}
    		
    		// 根节点左子树中节点的个数
    		int leftLength = rootInIndex - startInIndex;  
    		// 确定前序遍历数组中左子树结束位置的下标
    		int leftPreOrderEndIndex = startPreIndex + leftLength; 
    		
    		if(leftLength > 0){
    			// 构建左子树
    			root.leftNode = constructCore(preOrder, startPreIndex + 1, leftPreOrderEndIndex, 
    							inOrder, startInIndex, rootInIndex - 1);
    		}
    		
    		if(leftLength < endPreIndex - startPreIndex){
    			// 右子树有元素，构建右子树
    			root.rightNode = constructCore(preOrder, leftPreOrderEndIndex + 1, endPreIndex, 
    					              inOrder, rootInIndex + 1, endInIndex); 
    		}
    		return root;   // 返回构建好的二叉树的根节点 root
    	}
    	
    	/**
    	 * 前序打印二叉树
    	 */
    	
    	public static void printPreOrder(BinaryTree root) {
            if (root == null) {
                return;
            } else {
                System.out.print(root.value + " ");
            }
            if (root.leftNode != null) {
                printPreOrder(root.leftNode);
            }
            if (root.rightNode != null) {
                printPreOrder(root.rightNode);
            }
        }
    	
    	/**
    	 * 测试
    	 */
    	public static void main(String[] args) throws Exception{
    		ReConstructBinaryTree rcbt = new ReConstructBinaryTree();
    		
    		int[] preOrder = {1, 2, 4, 7, 3, 5, 6, 8};   // 前序遍历数组
    		int[] inOrder = {4, 7, 2, 1, 5, 3, 8, 6};    // 中序遍历数组
    		
    		printPreOrder(reConstruct(preOrder, inOrder, preOrder.length));
    	}
    }

在constructCore函数中，我们先根据先序遍历的第一个数字创建根节点，接下来在中序遍历中找到根节点的位置，这样就能确定左右子树节点的数量。在前序遍历和中序遍历的序列中划分左右子树节点的值之后，我们就可以递归调用函数constructCore，去分别构建它的左右子树。

[20181231110905699.png]: /images/20220401/a6b9f34a03ab4fc6991fa4f41e91cb52.png