JAVA练习315- 从前序与中序遍历序列构造二叉树

题目概览

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

示例 1:

输入:preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出:[3,9,20,null,null,15,7]

示例 2:

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

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder和inorder均无重复元素
• inorder均出现在preorder
• preorder保证为二叉树的前序遍历序列
• inorder保证为二叉树的中序遍历序列

来源：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

解题分析

方法：模拟

前序是：根 - 左 - 右，中序是 左 - 根 - 右。我们可以根据前序数组第一个元素拿到根节点，然后再到中序数组中进行拆分，我们定义前序数组的范围为 [ pi, pj ]，中序数组的范围为 [ ii, ij ]，中序数组中根节点的索引为 root，那么可以得到每个子数组的范围：

• 中序子数组 - 左 ：[ ii, root - 1 ]
• 中序子数组 - 右 ：[ root + 1, ij ]
• 前序子数组 - 左 ：[ pi + 1, pi + root - ii ]
• 前序子数组 - 右 ：[ pi + 1 + root - ii, pj ]

将这个范围作为参数继续往下传，然后重复拿根节点+拆分的操作即可，直到数组为空或只有一个元素停止。

时间复杂度：O(n)
空间复杂度：O(n)

/** * 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; if (n == 0) { return null; } return buildTree(preorder, inorder, 0, n - 1, 0, n - 1); } public TreeNode buildTree(int[] preorder, int[] inorder, int pi, int pj, int ii, int ij) { if (pi > pj || ii > ij) { return null; } TreeNode node = new TreeNode(preorder[pi]); if (pi == pj || ii == ij) { return node; } int root = preorder[pi]; int rootIndex = ii; for (int i = ii; i <= ij; ++i) { if (root == inorder[i]) { rootIndex = i; } } node.left = buildTree(preorder, inorder, pi + 1, pi + rootIndex - ii, ii, rootIndex - 1); node.right = buildTree(preorder, inorder, pi + rootIndex - ii + 1, pj, rootIndex + 1, ij); return node; } }