力扣105. 从前序与中序遍历序列构造二叉树（Java实现）

105. 从前序与中序遍历序列构造二叉树

1. 思路

				a
              /	  \
             b     c
           /  \   / \		
        null  d  e  null

pre		[a		b		d		c		e]
in		[b		d		a		e		c] 
         0		1		2		3		4           

上面给出一棵树，以及它的先序遍历数组和中序遍历数组。

先序数组的第一个元素a就是树的根节点，而a位于中序数组索引2的位置上。

说明中序数组索引 [0,1] 范围上，是a的左树。

					f(pre,0,4,in,0,4)
                  /					\
   f(pre，1，2，in，0，1)            f(pre,3,4,in,3,4)

这个递归函数是这样的。

f(pre,0,4,in,0,4) 是根据先序数组索引[0,4] 范围上 以及中序数组索引[0,4] 范围上 的元素建树，并将头节点返回。

根据上面的分析，我们知道中序数组索引 [0,1] 范围上，是a的左树。那么先序数组中a元素后面的两个元素就是左树。

所以f(pre,0,4,in,0,4) 递归调用 f(pre，1，2，in，0，1) 。

f(pre，1，2，in，0，1) 的 返回结果是 a 的左子树的头节点。之后让a.left指向它即可。

f(pre，1，2，in，0，1) 返回结果后，f(pre,0,4,in,0,4) 再递归调用f(pre,3,4,in,3,4)。

将f(pre,3,4,in,3,4)的返回结果作为a的右孩子。

那我们该怎么求子树的索引范围呢？

pre		[h					]
		 l1				   r1
         
in		[		 h			]  
    	 l2		 k	       r2

h 就是树的头节点。

f(pre，l1，r1，in，l2，r2) 会将建好树的头节点返回。

h的左子树在in数组中索引范围为[l2, k-1]，总共 k - l2 个数。

那h的左子树在pre数组中的索引范围为 [l1 + 1, l1 + k - l2]。

h的右子树在pre数组中的索引范围为[l1 + k - l2 + 1, r1]

h的右子树在in数组中的索引范围为[k+1, r2]

2. 代码

	public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length){
            return null;
        }

        /**
         * map里存放的是中序遍历的节点值和其在中序数组的索引
         * 先序数组的第一个元素是头节点
         * 而头节点在中序数组的索引可以通过map.get(头节点的值) 获得
         */
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return f(preorder,0,preorder.length-1,inorder,0,inorder.length-1,map);
    }

    private static TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2, HashMap<Integer,Integer> map) {
        if (l1 > r1){
            return null;
        }

        TreeNode head = new TreeNode(preorder[l1]);

        if (l1 == r1){
            return head;
        }

        int k = map.get(preorder[l1]);

        head.left = f(preorder, l1 + 1, l1 + k - l2, inorder, l2, k-1, map);
        head.right = f(preorder, l1 + k - l2 + 1 , r1, inorder, k + 1, r2, map);

        return head;
    }