算法005

描述

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

例子

Input:
	preorder：{3,9,20,15,7}
	inorder：{9,3,15,20,7}
Output:
	该二叉树

思路

根据先序遍历确定根，再通过中序遍历将数组划分为两部分，分别是左子树、右子树。 故可以通过一个HashMap存储中序遍历的数组值与下标，key为值，value为下标。

代码

class TreeNode {
    private TreeNode leftChild;
    private TreeNode rightChild;
    private int value;

    public TreeNode(int value) {
        this.value = value;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

public class Question005 {
	//中序遍历结果，用来对二叉树进行划分，左右子树
    //为了方便快速的找出根结点对应的下标，来确定左右子树结点个数
    private static HashMap<Integer, Integer> preorderMap = new HashMap<>();
    public static void main(String[] args) {
        int [] preorder = new int[] {3,9,20,15,7};
        int [] inorder = new int[] {9,3,15,20,7};

        for (int i = 0; i < preorder.length; i++) {
            preorderMap.put(inorder[i],i);
        }
        TreeNode root = reConstructBinaryTree(preorder,0, preorder.length);
    }
    /**
     * pre：前序遍历数组
     * preL：二叉树起始结点下标
     * length：长度
     */
    public static TreeNode reConstructBinaryTree(int [] pre, int preL, int length) {
        if (length == 1) {
            return new TreeNode(pre[preL]);
        }
        TreeNode root = new TreeNode(pre[preL]);
        Integer index = preorderMap.get(root.getValue());
        int leftLength = index - preL;
        root.setLeftChild(reConstructBinaryTree(pre,preL+1,leftLength));
        root.setRightChild(reConstructBinaryTree(pre,index+1,length-leftLength-1));
        return root;
    }
}