【算法】重建二叉树并进行后序遍历的Java实现

简介: 【算法】重建二叉树并进行后序遍历的Java实现

在二叉树的问题中,给定二叉树的前序遍历(Preorder)和中序遍历(Inorder)序列,如何求得其后序遍历(Postorder)序列是一个经典的面试题。本文将详细介绍如何通过Java实现这一过程。


问题描述

前序遍历(Preorder):按根节点 -> 左子树 -> 右子树的顺序访问节点。

中序遍历(Inorder):按左子树 -> 根节点 -> 右子树的顺序访问节点。

后序遍历(Postorder):按左子树 -> 右子树 -> 根节点的顺序访问节点。


给定前序遍历和中序遍历序列,我们需要构建二叉树并输出其后序遍历序列。

实现思路

  1. 重建二叉树:利用前序遍历和中序遍历的特性,通过递归方法重建二叉树。
  2. 后序遍历二叉树:通过递归方法进行后序遍历并输出结果。

实现步骤

1. 重建二叉树

首先,我们通过前序遍历的第一个元素确定根节点。在中序遍历中找到该根节点的位置,可以将中序遍历数组分为左子树和右子树两部分。递归地对这两部分继续构建左右子树。

2. 后序遍历

在构建好的二叉树上进行后序遍历,按左子树 -> 右子树 -> 根节点的顺序输出节点值。

代码实现

以下是完整的Java实现代码:

import java.util.HashMap;
import java.util.Map;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
public class BinaryTree {
    private int preIndex = 0;
    private Map<Integer, Integer> inorderIndexMap = new HashMap<>();
 
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, 0, inorder.length - 1);
    }
 
    private TreeNode buildTreeHelper(int[] preorder, int inorderStart, int inorderEnd) {
        if (inorderStart > inorderEnd) {
            return null;
        }
        
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        int inorderIndex = inorderIndexMap.get(rootVal);
        
        root.left = buildTreeHelper(preorder, inorderStart, inorderIndex - 1);
        root.right = buildTreeHelper(preorder, inorderIndex + 1, inorderEnd);
        
        return root;
    }
 
    public void postorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
 
    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.buildTree(preorder, inorder);
        
        System.out.println("Postorder traversal:");
        binaryTree.postorderTraversal(root);
    }
}

代码解释

  1. TreeNode类:定义二叉树节点的数据结构。
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

BinaryTree类:包含重建二叉树和后序遍历的方法。

  • buildTree 方法:接受前序遍历和中序遍历数组,构建并返回二叉树的根节点。
  • buildTreeHelper 方法:递归地构建二叉树。
  • postorderTraversal 方法:递归地进行后序遍历,并输出节点值。
  1. buildTreeHelper方法:通过前序遍历的当前节点值和中序遍历的索引,递归地构建左右子树。
private TreeNode buildTreeHelper(int[] preorder, int inorderStart, int inorderEnd) {
    if (inorderStart > inorderEnd) {
        return null; // Base case: no elements to construct the tree
    }
 
    int rootVal = preorder[preIndex++]; // Get the current root value from preorder traversal
    TreeNode root = new TreeNode(rootVal); // Create the root node
    int inorderIndex = inorderIndexMap.get(rootVal); // Find the index of the root in inorder traversal
 
    // Recursively build the left subtree
    root.left = buildTreeHelper(preorder, inorderStart, inorderIndex - 1);
    // Recursively build the right subtree
    root.right = buildTreeHelper(preorder, inorderIndex + 1, inorderEnd);
 
    return root;
}

后序遍历:通过递归方法进行后序遍历,按照左子树 -> 右子树 -> 根节点的顺序输出节点值。

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

main方法:创建前序遍历和中序遍历数组,调用buildTree方法构建二叉树,然后调用postorderTraversal方法输出后序遍历结果。

public static void main(String[] args) {
    int[] preorder = {3, 9, 20, 15, 7};
    int[] inorder = {9, 3, 15, 20, 7};
    
    BinaryTree binaryTree = new BinaryTree();
    TreeNode root = binaryTree.buildTree(preorder, inorder);
    
    System.out.println("Postorder traversal:");
    binaryTree.postorderTraversal(root);
}

总结

通过上述步骤,我们可以实现根据前序遍历和中序遍历序列重建二叉树,并输出其后序遍历序列。这不仅帮助我们加深对二叉树遍历的理解,也为处理相关面试题提供了一个有力的工具。希望这篇文章对你有所帮助!

相关文章
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
92 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
1月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
58 5
|
1月前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
38 2
|
1月前
|
存储 Java 开发者
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
45 0
|
2月前
|
Java 程序员 编译器
Java|如何正确地在遍历 List 时删除元素
从源码分析如何正确地在遍历 List 时删除元素。为什么有的写法会导致异常,而另一些不会。
39 3
|
2月前
|
前端开发 小程序 Java
java基础:map遍历使用;java使用 Patten 和Matches 进行正则匹配;后端传到前端展示图片三种情况,并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配,以及后端向前端传输图片并保存到手机的三种情况。
27 1
|
1月前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
19 0
|
6月前
|
缓存 Java 测试技术
探讨Java中遍历Map集合的最快方式
探讨Java中遍历Map集合的最快方式
92 1