【LeetCode 105】算法：从前序与中序遍历序列构造二叉树
题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。根据给定的先序遍历（preorder）和中序遍历（inorder）数组来重建二叉树是一个经典的算法问题。先序遍历的第一个元素总是树的根节点，而中序遍历可以帮我们确定根节点的左子树和右子树的边界。
首先创建一个TreeNode类来表示二叉树的节点。
然后，定义一个Solution类，其中包含buildTree方法来根据给定的先序和中序遍历数组构建二叉树。
buildTreeHelper方法是一个递归方法，它使用先序遍历的起始和结束索引（preStart和preEnd）以及中序遍历的起始和结束索引（inStart和inEnd）来构建子树。
使用一个HashMap（inMap）来存储中序遍历中每个值对应的索引，这样我们可以快速找到根节点在中序遍历中的位置，并据此分割左右子树。
Java代码实现：
import java.util.HashMap;
import java.util.Map;
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
Map<Integer, Integer> inMap; // 用于存储中序遍历中值到索引的映射
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
inMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inMap.put(inorder, i);
}
return buildTreeHelper(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder);
int inRoot = inMap.get(root.val); // 找到根节点在中序遍历中的位置
int numsLeft = inRoot - inStart; // 左子树的节点数目
root.left = buildTreeHelper(preorder, preStart + 1, preStart + numsLeft, inStart, inRoot - 1);
root.right = buildTreeHelper(preorder, preStart + numsLeft + 1, preEnd, inRoot + 1, inEnd);
return root;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] preorder = {3, 9, 20, 15, 7};
int[] inorder = {9, 3, 15, 20, 7};
TreeNode root = solution.buildTree(preorder, inorder);
// 打印树的先序遍历，用于验证结果
System.out.print("Preorder traversal of the constructed tree: ");
preorderTraversal(root);
}
// 先序遍历打印二叉树
public static void preorderTraversal(TreeNode root) {
if (root == null) {
System.out.print("null ");
return;
}
System.out.print(root.val + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
页:
[1]