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

题目描述

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

思路分析

我们可以利用前序遍历和后序遍历的特点来构造二叉树：

  1. 前序遍历的第一个元素是根节点。
  2. 后序遍历的最后一个元素是根节点。
  3. 前序遍历的第二个元素是左子树的根节点。
  4. 后序遍历中左子树的根节点的位置可以帮助我们确定左子树的范围。

通过递归的方法，我们可以不断地分割前序和后序数组来构造二叉树。

在代码中，L 变量用于找到左子树的根节点在后序遍历中的位置。我们需要加 1 的原因是：

  • 在后序遍历中，左子树的根节点的位置是 i，而左子树的范围是从 0 到 i。
  • 因此，左子树的长度是 i + 1，我们需要在前序遍历中取出前 i + 1 个元素来构造左子树。

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21



func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
	if len(preorder) <= 0 || len(postorder) <= 0 {
		return nil
	}
	root := &TreeNode{Val: preorder[0]}
	// 非常重要
	if len(preorder) == 1 {
		return root
	}
	// L 变量用于找到左子树的根节点在后序遍历中的位置
	L := 0
	for i := range postorder {
		if postorder[i] == preorder[1] {
			L = i + 1
			break
		}
	}
	root.Left = constructFromPrePost(preorder[1:L+1], postorder[:L])
	root.Right = constructFromPrePost(preorder[L+1:], postorder[L:len(postorder)-1])
	return root
}





1



write your code here

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2024/58828253
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！