【Leetcode 热题 100】105. 从前序与中序遍历序列构造二叉树

devtools/2024/12/23 23:45:27/

问题背景

给定两个整数数组 $p reor d er$ 和 $in or d er$ ，其中 $p reor d er$ 是二叉树的 先序遍历， $in or d er$ 是同一棵树的 中序遍历，请构造二叉树并返回其根节点。

数据约束

$\le preorder.length \le 3000$
$in or d er . l e n g t h = p reor d er . l e n g t h$
$\le preorder[i], inorder[i] \le 3000$
$p reor d er$ 和 $in or d er$ 均 无重复 元素
$in or d er$ 均出现在 $p reor d er$
$p reor d er$ 保证为二叉树的前序遍历序列
$in or d er$ 保证为二叉树的中序遍历序列

解题过程

大体上的流程就是不断地从先序序列中确定根节点，再从中序序列中根据这个根节点的位置去划分左右子树，这样就能构建每一棵子树。
需要注意的是，用哈希表存储中序序列中每个节点出现的位置，能够避免在递归的过程中再用循环查找，能够提高效率。
通过这道题体会到的是，保证方法实现的正确性之后，剩下只要调用的时候填对参数就行了。

碎碎念：几年前第一次看这个实现的时候一窍不通，难过地掉头发。如今能不看题解自己想到定义哈希表，完整地实现出来，原来从不得其门而入到现在已经过去这么久了……

具体实现

/*** Definition for a binary tree node.* 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 {public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 能够确定长度的列表，在初始化的时候就定好，尽可能地避免扩容，养成好习惯Map<Integer, Integer> map = new HashMap<>(n);for(int i = 0; i < n; i++) {map.put(inorder[i], i);}return dfs(preorder, 0, n, 0, n, map);}private TreeNode dfs(int[] preorder, int preL, int preR, int inL, int inR, Map<Integer, Integer> map) {if(preL == preR) {return null;}// 根据左子树中元素的数量来确定某几个参数，体会一下偏移的思想int leftCount = map.get(preorder[preL]) - inL;// 其中有几个参数要加一，是因为要跳过当前节点本身TreeNode left = dfs(preorder, preL + 1, preL + 1 + leftCount, inL, inL + leftCount, map);TreeNode right = dfs(preorder, preL + 1 + leftCount, preR, inL + 1 + leftCount, inR, map);return new TreeNode(preorder[preL], left, right);}
}