889. 根据前序和后序遍历构造二叉树

🟠   🔖  树 数组 哈希表 分治 二叉树  🔗 力扣 LeetCode

题目

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]

Output: [1]

Constraints:

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• All the values of preorder are unique.
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• All the values of postorder are unique.
• It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

题目大意

1. 前序遍历 (preorder)：[根, 左子树, 右子树]
2. 后序遍历 (postorder)：[左子树, 右子树, 根]
3. 由于没有 中序遍历，无法直接区分左、右子树的边界，但可以利用 preorder[1]（前序的第二个元素）来确定左子树的根节点在 postorder 中的位置。

• 设 preorder[0] 是根节点 root，创建 TreeNode(root).
• preorder[1] 是左子树的根，查找 postorder 中 preorder[1] 的位置 idx。
• postorder[0] ~ postorder[idx] 是左子树，postorder[idx+1] ~ postorder[n-2] 是右子树。
• 递归构造左右子树。

复杂度分析

• 时间复杂度：O(n)，每个节点只访问一次。
• 空间复杂度：O(n)，递归栈深度最多 O(n)。

代码

/**
 * @param {number[]} preorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var constructFromPrePost = function (preorder, postorder) {
	if (!preorder.length || !postorder.length) return null;
	let preIndex = 0;
	let postIndex = 0;

	const buildTree = () => {
		let root = new TreeNode(preorder[preIndex++]);
		if (root.val !== postorder[postIndex]) {
			root.left = buildTree();
		}

		if (root.val !== postorder[postIndex]) {
			root.right = buildTree();
		}

		postIndex++;
		return root;
	};

	return buildTree();
};