LeetCode第106题：从中序与后序遍历序列构造二叉树的Java实现

摘要

LeetCode第106题要求使用一棵树的中序遍历和后序遍历序列来重建二叉树。本文将介绍两种Java实现方法：递归和迭代。

1. 问题描述

给定一棵树的中序遍历和后序遍历序列，重建出这棵树的唯一二叉树结构。

2. 示例分析

输入：[1,2,4]（中序遍历）和[4,2,1]（后序遍历）
输出：[2,1,null,null,3]

3. 算法设计

3.1 递归法

递归法利用后序遍历的最后一个元素是树的根节点，然后在中序遍历中找到根节点的位置，将树分为左右子树。

3.2 迭代法

迭代法使用栈来模拟递归过程，通过维护当前遍历的子树的范围，逐步构建整棵树。

4. Java代码实现

4.1 递归法

   class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) { val = x; }
}

4.2 迭代法

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }
        
        TreeNode[] nodes = new TreeNode[inorder.length];
        for (int i = 0; i < inorder.length; i++) {
            nodes[i] = new TreeNode(inorder[i]);
        }
        
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode root = nodes[postorder.length - 1];
        stack.push(root);
        
        int postIndex = postorder.length - 2;
        
        for (int i = inorder.length - 2; i >= 0; i--) {
            TreeNode node = nodes[i];
            while (!stack.isEmpty() && stack.peek().val < node.val) {
                node.left = stack.pop();
            }
            stack.push(node);
            postIndex--;
        }
        
        return root;
    }
}

5. 代码解析

• 递归法：通过递归调用buildTreeHelper方法，利用后序遍历的最后一个元素作为根节点，然后在中序遍历中找到根节点的位置，递归地构建左右子树。
• 迭代法：使用栈来模拟递归过程，从后序遍历的最后一个元素开始，逐步构建整棵树。

6. 测试验证

使用LeetCode平台或其他测试工具对提供的代码进行测试，确保算法的正确性。

7. 总结

LeetCode第106题是一个典型的树重建问题，通过理解二叉树的遍历特性，可以有效地利用中序和后序遍历序列重建二叉树。递归法直观易理解，而迭代法则更节省空间。

8. 参考文献

• LeetCode第106题官方题解
• 二叉树遍历

---

原文地址：https://blog.csdn.net/2301_77695569/article/details/140508180

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！