算法笔记，前序与中序遍历构造二叉树

算法笔记，前序与中序遍历构造二叉树 本资源主要讲解了如何使用前序遍历和中序遍历来构造二叉树的算法，并提供了Java和Python的实现代码。下面是对该算法的详细解释： 二叉树的遍历规则 在解决这个问题之前，我们首先需要了解二叉树的遍历规则。二叉树的遍历规则有三种：前序遍历、中序遍历和后序遍历。 * 前序遍历的顺序为：根节点 -> 左子树 -> 右子树 * 中序遍历的顺序为：左子树 -> 根节点 -> 右子树 * 后序遍历的顺序为：左子树 -> 右子树 -> 根节点 问题描述 给定两个整数数组`preorder`和`inorder，其中`preorder`是二叉树的前序遍历，`inorder`是同一棵树的中序遍历。构造二叉树并返回其根节点。 解决方法 我们可以使用递归的方法来解决这个问题。我们需要找到根节点在中序遍历中的位置，然后递归地构造左子树和右子树。 在中序遍历中对根节点进行定位时，我们可以使用哈希表来快速地定位根节点。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们只需要O(1)的时间对根节点进行定位。 Java实现代码 ```java public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } class Solution { private Map<Integer, Integer> indexMap; public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return null; } // 前序遍历中的第一个节点就是根节点 int preorder_root = preorder_left; // 在中序遍历中定位根节点 int inorder_root = indexMap.get(preorder[preorder_root]); // 先把根节点建立出来 TreeNode root = new TreeNode(preorder[preorder_root]); // 得到左子树中的节点数目 int size_left_subtree = inorder_root - inorder_left; // ... } } ``` Python实现代码 ```python class Solution: def buildTree(self, preorder, inorder): if not preorder: return None root = TreeNode(preorder[0]) inorder_index = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1:inorder_index+1], inorder[:inorder_index]) root.right = self.buildTree(preorder[inorder_index+1:], inorder[inorder_index+1:]) return root ``` 复杂度分析 时间复杂度：O(n)，其中 n 是树中的节点个数。 空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。