leetcode hot100【LeetCode 105.从前序与中序遍历序列构造二叉树】java实现

LeetCode 105.从前序与中序遍历序列构造二叉树

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点

示例1：

输入:
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7]3/ \9  20/  \15   7

示例2：

输入: preorder = [-1], inorder = [-1]
输出: [-1]

Java 实现代码

class Solution {private Map<Integer, Integer> inorderIndexMap;public TreeNode buildTree(int[] preorder, int[] inorder) {inorderIndexMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {inorderIndexMap.put(inorder[i], i);}return buildSubTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1);}private TreeNode buildSubTree(int[] preorder, int preStart, int preEnd, int inStart, int inEnd) {if (preStart > preEnd || inStart > inEnd) {return null;}// 根节点是前序遍历的第一个元素int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);// 在中序遍历中找到根节点的位置int rootIndex = inorderIndexMap.get(rootVal);int leftSubtreeSize = rootIndex - inStart;// 构造左子树root.left = buildSubTree(preorder, preStart + 1, preStart + leftSubtreeSize, inStart, rootIndex - 1);// 构造右子树root.right = buildSubTree(preorder, preStart + leftSubtreeSize + 1, preEnd, rootIndex + 1, inEnd);return root;}
}

解题思路

1. 前序遍历的性质:

   • 前序遍历的第一个元素为当前二叉树的根节点。

2. 中序遍历的性质:

   • 根节点将中序遍历序列划分为左子树和右子树。
   • 根节点左侧部分是左子树的中序遍历，右侧部分是右子树的中序遍历。

3. 构造过程:

   • 从前序遍历中提取根节点。
   • 在中序遍历中找到根节点，确定左右子树的边界。
   • 递归地构造左右子树。

复杂度分析

• 时间复杂度: 每个节点在构造过程中都只会访问一次，同时使用了哈希表快速查找中序遍历中节点的索引。

  • 构造树的时间复杂度为 O(n)，其中 n 是节点数。
  • 构造哈希表的时间复杂度为 O(n)。

• 空间复杂度:

  • 递归调用的空间复杂度为 O(h)，其中 h 是树的高度，最坏情况下为 O(n)，平均情况下为 O(log n)。
  • 哈希表的空间复杂度为 O(n)。因此，总的空间复杂度为 O(n)。