java前序遍历和中序遍历

Java前序遍历和中序遍历是二叉树遍历的两种方式，它们在数据结构和算法中都非常重要。

前序遍历是指，首先访问根节点，然后遍历左子树，再遍历右子树。具体过程可以通过递归实现。在Java中，可以使用TreeNode类来表示二叉树节点，在前序遍历中，代码实现如下：

public void preOrder(TreeNode root) {
if (root != null) {
System.out.println(root.val);
preOrder(root.left);
preOrder(root.right);
}
}

中序遍历是指，首先遍历左子树，然后访问根节点，再遍历右子树。同样，具体过程可以通过递归实现。在Java中，中序遍历的代码实现如下：

public void inOrder(TreeNode root) {
if (root != null) {
inOrder(root.left);
System.out.println(root.val);
inOrder(root.right);
}
}

前序遍历和中序遍历在实际应用中经常被用来实现查找、删除和修改等操作，例如根据前序遍历和中序遍历的结果构建二叉树，或者使用中序遍历输出二叉搜索树的节点值，都是比较常见的操作。因此，掌握Java前序遍历和中序遍历的实现方式，有助于我们更好地理解树结构的特点和应用场景。

相关问题

Java实现前序遍历、中序遍历和后序遍历。

二叉树的遍历方式有三种：前序遍历、中序遍历和后序遍历。Java实现这三种遍历方式的代码如下：

前序遍历：

public void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

中序遍历：

public void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

后序遍历：

public void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

其中，TreeNode是二叉树的节点类，val表示节点的值，left和right分别表示左子树和右子树。

用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);
}
}