用java实现根据二叉树前序遍历输出中序遍历

题目描述

给定二叉树的前序遍历输出，求二叉树的中序遍历输出。

示例

输入：[3,9,20,null,null,15,7]
输出：[9,3,15,20,7]

解题思路

根据二叉树的前序遍历和中序遍历可以唯一确定一颗二叉树。因此，我们可以利用前序遍历找到根节点，然后在中序遍历中找到根节点的位置，以此划分出左子树和右子树的中序遍历，然后递归处理左右子树即可。

具体实现步骤如下：

- 使用递归函数实现。
- 找到前序遍历的第一个节点作为根节点。
- 在中序遍历中找到根节点的位置，以此划分出左子树和右子树的中序遍历。
- 分别递归处理左子树和右子树，并将结果保存在一个 List 中。
- 最后返回 List。

Java 代码实现

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(int[] preorder) {
if (preorder == null || preorder.length == 0) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
TreeNode root = buildTree(preorder, 0, preorder.length - 1);
inorder(root, res);
return res;
}

private TreeNode buildTree(int[] preorder, int start, int end) {
if (start > end) {
return null;
}
TreeNode root = new TreeNode(preorder[start]);
int index = start;
while (index <= end && preorder[index] <= preorder[start]) {
index++;
}
root.left = buildTree(preorder, start + 1, index - 1);
root.right = buildTree(preorder, index, end);
return root;
}

private void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}