力扣——从前序与中序遍历序列构造二叉树

力扣——从前序与中序遍历序列构造二叉树

引用

CSDN

1.

https://blog.csdn.net/weixin_49332521/article/details/145646360

题目描述

解题思路

方法一：递归实现

1. 根据前序遍历可以确定根节点
2. 在中序遍历中找到根节点，从而确定左右子树的区间
3. 知道左右子树的区间后，分别在前序遍历中查找左右子树的根节点，然后递归构建左右子树

这种方法的核心是通过递归不断缩小问题规模，每次递归都需要确定当前子树的根节点以及左右子树的边界。

方法二：栈与指针实现

1. 前序遍历顺序为“中左右”，中序遍历顺序为“左中右”
2. 假设没有右子树，前序和中序的结果是相反的
3. 前序遍历是从上到下，中序遍历是从下到上，两者是逆序关系
4. 当中序遍历的顺序被打破时，说明出现了右子树，此时中序遍历中打破逆序的节点就是其前一个节点的右子节点

这种方法通过栈来辅助实现，具体步骤如下：

1. 将前序遍历的节点依次入栈，每个入栈的节点都暂时当作根节点处理
2. 当栈顶节点与中序遍历的第一个节点相同时，说明这是树最左下的节点
3. 在前序遍历中，这个最左下节点后面的节点（即下一个入栈的节点）必定是一个右子节点
4. 通过在中序遍历中寻找打破逆序的位置，可以确定右子节点的父节点

代码实现

方法一：递归实现

class Solution {
    private Map<Integer, Integer> indexMap;

    // 除了数组，其他参数都是下标
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

方法二：栈与指针实现

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            //入栈，注意是栈顶比较
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                //寻找逆序
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}

代码详解：

• 方法一：通过递归实现，主要利用了前序遍历和中序遍历的特点。前序遍历的第一个元素是根节点，通过在中序遍历中找到根节点的位置，可以确定左右子树的范围。然后递归地对左右子树进行相同的操作。

• 方法二：通过栈来辅助实现。核心思想是利用前序遍历和中序遍历的顺序关系。前序遍历是从上到下，中序遍历是从下到上，当中序遍历的顺序被打破时，说明出现了右子树。通过栈来维护当前处理的节点，并根据中序遍历的顺序来确定右子节点的位置。