一、题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
限制：
0 <= 节点个数 <= 5000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路
1）我们先明确下：
前序遍历 根-左子树-右子树
中序遍历 左子树-根-右子树
2）所以我们能够很快明确 3 即为我们的根节点 root。
3）那么现在我们来思考，如果希望从中序遍历中获取到根节点的位置要怎么做呢？其实这里你应该考虑到的一点就是 题目强调的非重复，如果是重复的话比如根节点重复的话，就会变的更加复杂了。
我们来看题目说非重复的，也就是说我们的根节点只有 3，那么如何能够很快的查找到它对应的位置，我们想到了数组(如果已知下标的话)，或者字典我们根据 key 直接获取 value。这里我们可以采用字典维护中序遍历的所有值和下标，也就是节点值为 key，数组下标为 value。
4）我们接下来可以直接从字典表中获取到数组下标 value，并能明确知道左子树的长度范围和右子树的长度范围。
5）然后继续我们刚才的 2-3-4 这几个步骤
6）很清楚的可以看到 5 这里面会涉及到递归，退出条件为如果前序遍历的左下标大于前序遍历的右下标即为 null。
三、代码实现
class TreeNode { int val; TreeNode left; TreeNode right;
TreeNode(int x) { this.val = x; } } private HashMap<Integer, Integer> index; /** * 处理思路主要是我们明确一点就是前序遍历则第一个节点一定是根节点。 * * @param preorder * @param inorder * @return */ public TreeNode buildTree(int[] preorder, int[] inorder) { //第一步边界条件 if (preorder.length < 1 || inorder.length < 1) { return null; } //第二步、构造存储中序遍历的所有节点 index = new HashMap<>(preorder.length);
for (int i = 0; i < inorder.length; i++) { index.put(inorder[i], i); } //第三步、开始重建二叉树 return buildBinaryTree( preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1); }
private TreeNode buildBinaryTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) { //递归退出条件 if (preLeft > preRight){ return null; } //3.1、获取根节点 // 前序遍历中的第一个节点就是根节点 int preorder_root = preorder[preLeft]; // 在中序遍历中定位根节点 int inorder_root = index.get(preorder_root); //3.2、从中序字典表中获取到中序的下标位置 int leftInOrderLengh = inorder_root - inLeft; // 3.3、先把根节点建立出来 TreeNode treeNode = new TreeNode(preorder_root); // 3.4、递归地构造左子树，并连接到根节点 // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素 treeNode.left = buildBinaryTree(preorder, inorder, preLeft + 1, preLeft + leftInOrderLengh, inLeft, inorder_root - 1); //3.5、 构建右子树 treeNode.right = buildBinaryTree(preorder, inorder, preLeft + leftInOrderLengh + 1, preRight, inorder_root+1, inRight); return treeNode; }
复制代码
四、小结
从代码来看，我们其实是依赖了外部的字典数据结构以及先序遍历条件和中序遍历条件。
官方答案还有另外一种思路，先不往下看你能想到么？递归《=》栈 实际上这两个是经常可以互转的。
那么我们上面明显用到了递归，那么如果说现在换成栈应该是怎么个操作流程呢？
根据前序遍历特性，假设 U 和 V 两个节点，那么我们很快能够知道 U 和 V 的 2 种关系：
具体实现可以参考官方代码，不赘述。
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || preorder.length == 0) { return null; } TreeNode root = new TreeNode(preorder[0]); Deque<TreeNode> stack = new LinkedList<TreeNode>(); stack.push(root); int inorderIndex = 0; for (int i = 1; i < preorder.length; i++) { int preorderVal = preorder[i]; TreeNode node = stack.peek(); if (node.val != inorder[inorderIndex]) { node.left = new TreeNode(preorderVal); stack.push(node.left); } else { while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) { node = stack.pop(); inorderIndex++; } node.right = new TreeNode(preorderVal); stack.push(node.right); } } return root; }}
作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-by-leetcode-s/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复制代码
复杂度分析
时间复杂度：O(n)，其中 n 是树中的节点个数。
空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(h)（其中 hh 是树的高度）的空间存储栈。这里 h<n，所以（在最坏情况下）总空间复杂度为 O(n)。
评论