从前序与中序遍历序列构造二叉树
题目要求
你需要根据给定的两个数组 preorder 和 inorder 来重建一棵二叉树。preorder 数组代表了这棵树的先序遍历结果，而 inorder 数组代表了同一棵树的中序遍历结果。你的任务是根据这两个遍历结果来构造原始的二叉树，并返回这棵树的根节点。
解题思路
为了根据 preorder（先序遍历）和 inorder（中序遍历）数组重建原始的二叉树，我们可以遵循以下步骤：
-
确定根节点：
- 先序遍历的第一个元素总是树的根节点。
-
在中序遍历中找到根节点：
- 在中序遍历数组中找到根节点的位置，这将数组分为两部分，左边是树的左子树，右边是树的右子树。
-
划分先序遍历数组：
- 根据中序遍历中左子树的节点数量，我们可以在先序遍历数组中划分出左子树和右子树对应的部分。
-
递归构造左右子树：
- 使用中序遍历中的左子树部分和先序遍历中对应的部分递归构造左子树。
- 使用中序遍历中的右子树部分和先序遍历中对应的部分递归构造右子树。
-
构建树并返回根节点：
- 递归地构建整棵树，最后返回根节点。
在实现时，我们需要注意以下几点：
- 递归的基本情况是当先序遍历或中序遍历数组为空时，返回
null。 - 我们可以使用哈希表来存储中序遍历中每个值对应的索引，这样可以快速定位根节点在中序遍历中的位置，从而优化查找时间。
- 每次递归时，我们都需要更新先序遍历和中序遍历数组中的子数组范围，以便正确地划分左右子树。
通过以上步骤，我们可以高效地重建出原始的二叉树结构。
Golang 版本
package main
import (
"fmt"
)
// TreeNode is the structure for tree nodes
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// buildTree constructs a binary tree from preorder and inorder traversal slices.
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 || len(inorder) == 0 {
return nil
}
// The first element in preorder is always the root.
rootVal := preorder[0]
root := &TreeNode{Val: rootVal}
// Find the index of the root in inorder slice.
i := 0
for ; i < len(inorder); i++ {
if inorder[i] == rootVal {
break
}
}
// Recursively build the left and right subtrees.
root.Left = buildTree(preorder[1:i+1], inorder[:i])
root.Right = buildTree(preorder[i+1:], inorder[i+1:])
return root
}
func main() {
// Example usage:
preorder := []int{3, 9, 20, 15, 7}
inorder := []int{9, 3, 15, 20, 7}
root := buildTree(preorder, inorder)
fmt.Println("Root value of the tree is:", root.Val)
// Output will be the root of the tree constructed which is 3 in this case.
}
这段代码定义了一个TreeNode结构体，表示树的节点，并实现了buildTree函数来根据给定的preorder和inorder数组重建二叉树。在main函数中，我们提供了一个使用示例，构建了一棵树，并打印出了树的根节点的值。
C++版本
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
unordered_map<int, int> inMap; // Maps value to its index in inorder
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// Build a map to store the value-index pairs for quick access
for (int i = 0; i < inorder.size(); i++) {
inMap[inorder[i]] = i;
}
return buildTree(preorder, 0, preorder.size() - 1, 0);
}
TreeNode* buildTree(vector<int>& preorder, int preStart, int preEnd, int inStart) {
if (preStart > preEnd) return NULL;
TreeNode* root = new TreeNode(preorder[preStart]);
int inRoot = inMap[root->val];
int numsLeft = inRoot - inStart;
root->left = buildTree(preorder, preStart + 1, preStart + numsLeft, inStart);
root->right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inRoot + 1);
return root;
}
};
int main() {
vector<int> preorder = {3, 9, 20, 15, 7};
vector<int> inorder = {9, 3, 15, 20, 7};
Solution solution;
TreeNode* root = solution.buildTree(preorder, inorder);
cout << "Root value of the tree is: " << root->val << endl;
// Output should be the root of the tree constructed which is 3 in this case.
// Remember to delete the allocated memory for the tree
// This part is omitted for brevity
return 0;
}
这段 C++代码定义了一个TreeNode结构体，表示树的节点，并实现了一个Solution类，其中包含了buildTree函数来根据给定的preorder和inorder数组重建二叉树。在main函数中，我们提供了一个使用示例，构建了一棵树，并打印出了树的根节点的值。注意，在实际应用中，你可能需要编写额外的代码来释放分配给树节点的内存。
Python 版本
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None
# The first element of preorder is always the root.
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
# Recursively build the left and right subtree.
root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
return root
# Example usage:
if __name__ == "__main__":
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
solution = Solution()
root = solution.buildTree(preorder, inorder)
print("Root value of the tree is:", root.val)
# Output should be the root of the tree constructed which is 3 in this case.
这段 Python 代码定义了一个TreeNode类，表示树的节点，并实现了一个Solution类，其中包含了buildTree方法来根据给定的preorder和inorder列表重建二叉树。在脚本的主部分，我们提供了一个使用示例，构建了一棵树，并打印出了树的根节点的值。
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 {
private Map<Integer, Integer> inMap = new HashMap<>();
private int preIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// Build a hashmap to store value -> its index relations
for (int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
return buildTree(preorder, 0, preorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int inStart, int inEnd) {
if (inStart > inEnd) return null;
// The current root is always the next element in the preorder sequence
TreeNode root = new TreeNode(preorder[preIndex++]);
// Root splits inorder list into left and right subtrees
int inIndex = inMap.get(root.val);
// Build left subtree
root.left = buildTree(preorder, inStart, inIndex - 1);
// Build right subtree
root.right = buildTree(preorder, inIndex + 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.println("Root value of the tree is: " + root.val);
// Output should be the root of the tree constructed which is 3 in this case.
}
}
这段 Java 代码定义了一个TreeNode类，表示树的节点，并实现了一个Solution类，其中包含了buildTree方法来根据给定的preorder和inorder数组重建二叉树。在main方法中，我们提供了一个使用示例，构建了一棵树，并打印出了树的根节点的值。
Rust 版本
use std::collections::HashMap; // Definition for a binary tree node. #[derive(Debug, PartialEq, Eq)] pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, } impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None, } } } struct Solution; impl Solution { pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> { let mut in_map = HashMap::new(); for (i, &val) in inorder.iter().enumerate() { in_map.insert(val, i); } let mut pre_idx = 0; Solution::build(&preorder, &mut pre_idx, 0, inorder.len() as i32 - 1, &in_map) } fn build( preorder: &Vec<i32>, pre_idx: &mut usize, in_start: i32, in_end: i32, in_map: &HashMap<i32, usize>, ) -> Option<Rc<RefCell<TreeNode>>> { if in_start > in_end { return None; } let root_val = preorder[*pre_idx]; let root = Rc::new(RefCell::new(TreeNode::new(root_val))); *pre_idx += 1; let in_root_idx = *in_map.get(&root_val).unwrap() as i32; root.borrow_mut().left = Solution::build(preorder, pre_idx, in_start, in_root_idx - 1, in_map); root.borrow_mut().right = Solution::build(preorder, pre_idx, in_root_idx + 1, in_end, in_map); Some(root) } } fn main() { let preorder = vec![3, 9, 20, 15, 7]; let inorder = vec![9, 3, 15, 20, 7]; let tree = Solution::build_tree(preorder, inorder); println!("Root value of the tree is: {:?}", tree.as_ref().map(|node| node.borrow().val)); // Output should be the root of the tree constructed which is 3 in this case. }
这段 Rust 代码定义了一个TreeNode结构体，表示树的节点，并实现了一个Solution结构体，其中包含了build_tree方法来根据给定的preorder和inorder向量重建二叉树。在main函数中，我们提供了一个使用示例，构建了一棵树，并打印出了树的根节点的值。注意，Rust 中的TreeNode使用了Rc和RefCell来允许可变共享所有权，这是 Rust 特有的内存安全策略的一部分。
总结
这种解法的关键在于理解先序遍历和中序遍历的特点，以及如何利用这些特点来确定树的结构。先序遍历给出了根节点的顺序，而中序遍历则确定了左右子树的分界。通过递归地应用这些规则，可以逐步构建出整棵树。