Leetcode每日一题-105（5.22-java版本）

leetcode第105题

题目要求：

根据一棵树的前序遍历与中序遍历构造二叉树。且树中无重复元素。（记着这句话很重要）

例如：

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

这种题型就是树的重构，根据树的前序遍历和中序遍历，然后构造出一颗树。根据我以前的刷题经验我的做法是如下这样的。这样的做法就是一种递归的思路。首先前序数组的首位就是根节点，然后根据前序数组的首位来找其在中序数组中的对应位置，根据对应位置，将中序数组的左边部分作为该根节点的左子树，右边部分作为该根节点的右子树。

解法一：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
          return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
   
   public TreeNode build(int[] pre,int pres,int pree,int[] in,int ins,int ine) {
	   if(pree<pres||ine<ins) {
		   return null;
	   }
	   TreeNode root = new TreeNode(pre[pres]);
	   for(int i = ins;i<=ine;i++) {
		   if(in[i]==pre[pres]) {
			   root.left = build(pre,pres+1,pres+i-ins,in,ins,i-1);
			   root.right = build(pre,pres+i-ins+1,pree,in,i+1,ine);
			   break;
		   }
	   }
	   return root;

    }
}

当然我们追求的是更好，而不是做出答案。所以分析可以看到上述的解法存在可改进的地方。每次我们找根节点在中序序列中的位置的时候都需要遍历一次数组，所以我们做出调整，用hashmap来保存中序数组中数的位置。这样的话，我们增加了o（n）的空间复杂度，但是降低了时间复杂度。

解法二：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1,map);
    }

    public TreeNode build(int[] pre,int pres,int pree,int[] in,int ins,int ine,HashMap<Integer,Integer> map) {
        if(pree<pres||ine<ins) {
            return null;
        }
        TreeNode root = new TreeNode(pre[pres]);
        int i = map.get(pre[pres]);
        root.left = build(pre,pres+1,pres+i-ins,in,ins,i-1,map);
        root.right = build(pre,pres+i-ins+1,pree,in,i+1,ine,map);
        return root;

    }
}

当然看到这里这个题的解题已经出来了，大致是这样的，有兴趣的可以看接下来的国外大神 StefanPochmann的神奇解法，他省略了上述解法中的hashmap但是达到了一样的效果。

解法三：

class Solution {
    private int in = 0;
    private int pre = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE);
    }
    private TreeNode build(int[] preorder, int[] inorder, int stop) {
        if (pre == preorder.length) return null; // pre走到preorder末尾
        if (inorder[in] == stop) { // in指针走到了停止点
            in++; // stop点废弃了，in推进一位
            return null;
        }
        TreeNode node = new TreeNode(preorder[pre++]);
        node.left = build(preorder, inorder, node.val);
        // 左子树的停止点是当前的根节点的值
        node.right = build(preorder, inorder, stop);
        // 右子树的停止点是当前树的停止点
        return node;        
    }
}

在这个解法中我们可以看到它并没有用到hashmap这样的数据结构，它的思路的关键之处在于：

它引入了关键点stop点。

中序数组中左子树的stop点就是当前根节点的值，但是右子树的stop点是当前节点的停止点。

该解法思路很新奇，可以手动推解画图。

好了今天的leetcode刷题的解析到此结束，欢迎各位提出更多见解。如果有想每日刷题的可以直接私信我拉群，大家一起刷一起总结。希望每道题型都可以做出java语言的最优解，方便大家探讨。

#leetcode刷题组队##腾讯##笔试题目#