【LeetCode 105】算法：从前序与中序遍历序列构造二叉树

题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

根据给定的先序遍历（preorder）和中序遍历（inorder）数组来重建二叉树是一个经典的算法问题。先序遍历的第一个元素总是树的根节点，而中序遍历可以帮我们确定根节点的左子树和右子树的边界。
首先创建一个TreeNode类来表示二叉树的节点。
然后，定义一个Solution类，其中包含buildTree方法来根据给定的先序和中序遍历数组构建二叉树。
buildTreeHelper方法是一个递归方法，它使用先序遍历的起始和结束索引（preStart和preEnd）以及中序遍历的起始和结束索引（inStart和inEnd）来构建子树。
使用一个HashMap（inMap）来存储中序遍历中每个值对应的索引，这样我们可以快速找到根节点在中序遍历中的位置，并据此分割左右子树。
Java代码实现：

1. import java.util.HashMap;
2. import java.util.Map;
4. // Definition for a binary tree node.
5. class TreeNode {
6.     int val;
7.     TreeNode left;
8.     TreeNode right;
9.     TreeNode(int x) { val = x; }
10. }
12. public class Solution {
13.     Map<Integer, Integer> inMap; // 用于存储中序遍历中值到索引的映射
15.     public TreeNode buildTree(int[] preorder, int[] inorder) {
16.         if (preorder == null || inorder == null || preorder.length != inorder.length) {
17.             return null;
18.         }
19.         inMap = new HashMap<>();
20.         for (int i = 0; i < inorder.length; i++) {
21.             inMap.put(inorder[i], i);
22.         }
23.         return buildTreeHelper(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
24.     }
26.     private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int inStart, int inEnd) {
27.         if (preStart > preEnd || inStart > inEnd) {
28.             return null;
29.         }
30.         TreeNode root = new TreeNode(preorder[preStart]);
31.         int inRoot = inMap.get(root.val); // 找到根节点在中序遍历中的位置
32.         int numsLeft = inRoot - inStart; // 左子树的节点数目
34.         root.left = buildTreeHelper(preorder, preStart + 1, preStart + numsLeft, inStart, inRoot - 1);
35.         root.right = buildTreeHelper(preorder, preStart + numsLeft + 1, preEnd, inRoot + 1, inEnd);
37.         return root;
38.     }
40.     public static void main(String[] args) {
41.         Solution solution = new Solution();
42.         int[] preorder = {3, 9, 20, 15, 7};
43.         int[] inorder = {9, 3, 15, 20, 7};
44.         TreeNode root = solution.buildTree(preorder, inorder);
45.         
46.         // 打印树的先序遍历，用于验证结果
47.         System.out.print("Preorder traversal of the constructed tree: ");
48.         preorderTraversal(root);
49.     }
51.     // 先序遍历打印二叉树
52.     public static void preorderTraversal(TreeNode root) {
53.         if (root == null) {
54.             System.out.print("null ");
55.             return;
56.         }
57.         System.out.print(root.val + " ");
58.         preorderTraversal(root.left);
59.         preorderTraversal(root.right);
60.     }
61. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！