关注Java领域相关技术 记录有趣的事情

LeetCode-106. 从中序与后序遍历序列构造二叉树

US-B.Ralph
US-B.Ralph
2020-09-25

问题地址

LeetCode每日一题/2020-09-25

LeetCode106. 从中序与后序遍历序列构造二叉树

问题描述

规则

  • 根据一棵树的中序遍历与后序遍历构造二叉树。

注意

  • 你可以假设树中没有重复的元素。

示例

  • 示例一：
给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回二叉树
    3
   / \
  9  20
    /  \
   15   7

解析

解题思路

  • 题目给定一个二叉树的中序遍历序列、后序遍历序列，且二叉树中元素没有重复；
  • 根据后序遍历序列常用算法，可以看到后序遍历序列的最后一个元素处理的是根节点。
if (root == null) return;
postorderTraversalForRecursive(root.left,list);
postorderTraversalForRecursive(root.right,list);
list.add(root.val);
  • 对于中序遍历序列来说，根节点的左边是左子树，根节点的右边是右子树；

  • 所以我们只要找到根节点在中序序列中的位置，然后分别构建根节点、左子树、右子树就可以构建一颗准确的二叉树。

数据操作分析

  • 找切割点：
    • 遍历中序序列，根据后序序列最后一个元素找出根节点在中序遍历序列中的索引，记为 delimiterInx；
  • 使用 delimiterInx 将中序遍历序列分为左中序序列和右中序序列；
    • 左中序序列的范围 [inorderBeginInx, delimiterInx)；
    • 右中序序列的范围 [inorderBeginInx+delimiterInx+1, inorderEndInx)；
  • 对于后序遍历序列，没有一个很明确的元素指定切割范围，但是后序遍历序列的长度等于中序序列的长度，故我们可以利用已经分好的左中序序列来分割后序遍历序列；
    • 左后序序列的范围 [postorderBeginInx, leftInorder.length);
    • 右后序序列的范围 [postorderBeginInx, postorderEndinx);
  • 递归处理左子树、右子树；

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode0106_ConstructBinaryTreeFromInorderAndPostorderTraversal {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0) return null;
        return traversalTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode traversalTree(int[] inorder, int inorderBeginInx, int inorderEndInx, int[] postorder, int postorderBeginInx, int postorderEndInx) {

        if (postorderBeginInx == postorderEndInx) return null;
        TreeNode rootNode = new TreeNode(postorder[postorderEndInx - 1]);
        if (postorderEndInx - postorderBeginInx == 1) return rootNode;

        //确定分割点
        int delimterInx;
        for (delimterInx = inorderBeginInx; delimterInx < inorderEndInx; delimterInx++) {
            if (inorder[delimterInx] == postorder[postorderEndInx - 1]) break;
        }

        //切割中序序列
        int leftInoderArrayBeginInx = inorderBeginInx;
        int leftInoderArrayEndInx = delimterInx;
        int rightInorderArrayBeginInx = delimterInx + 1;
        int rightInorderArrayEndInx = inorderEndInx;

        //切割后序序列
        int leftPostorderArrayBeginInx = postorderBeginInx;
        int leftPostorderArrayEndInx = postorderBeginInx + delimterInx - inorderBeginInx;
        int rightPostorderArrayBeginInx = leftPostorderArrayEndInx;
        int rightPostorderArrayEndInx = postorderEndInx - 1;

        rootNode.left = traversalTree(inorder, leftInoderArrayBeginInx, leftInoderArrayEndInx, postorder, leftPostorderArrayBeginInx, leftPostorderArrayEndInx);
        rootNode.right = traversalTree(inorder, rightInorderArrayBeginInx, rightInorderArrayEndInx, postorder, rightPostorderArrayBeginInx, rightPostorderArrayEndInx);

        return rootNode;
    }
}

官方解法

方法一：递归

思路：

  • 首先解决这道题我们需要明确给定一棵二叉树，我们是如何对其进行中序遍历与后序遍历的：
    • 中序遍历的顺序是每次遍历左孩子，再遍历根节点，最后遍历右孩子。
    • 后序遍历的顺序是每次遍历左孩子，再遍历右孩子，最后遍历根节点。
  • 写成代码的形式即：
// 中序遍历
void inorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inorder(root->left);
    ans.push_back(root->val);
    inorder(root->right);
}
// 后序遍历
void postorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    ans.push_back(root->val);
}
  • 因此根据上文所述，我们可以发现后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。

算法

  • 为了高效查找根节点元素在中序遍历数组中的下标，我们选择创建哈希表来存储中序序列，即建立一个（元素，下标）键值对的哈希表。
  • 定义递归函数 helper(in_left, in_right) 表示当前递归到中序序列中当前子树的左右边界，递归入口为helper(0, n – 1) ：
    • 如果 in_left > in_right，说明子树为空，返回空节点。
    • 选择后序遍历的最后一个节点作为根节点。
    • 利用哈希表 O(1)O(1) 查询当根节点在中序遍历中下标为 index。从 in_left 到 index – 1 属于左子树，从 index + 1 到 in_right 属于右子树。
    • 根据后序遍历逻辑，递归创建右子树 helper(index + 1, in_right) 和左子树 helper(in_left, index – 1)。注意这里有需要先创建右子树，再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。
    • 返回根节点 root。

复杂度分析：

  1. 时间复杂度:O(n)。其中 n 是树中的节点个数。

  2. 空间复杂度：O(n)。我们需要使用 O(n) 的空间存储哈希表，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 $h inorder[8] = 4`

    • 我们遍历 7，8 和 4。同理可得它们都是上一个节点（栈顶节点）的右儿子，所以它们会依次入栈。
      stack = [3, 20, 7, 8, 4]
      index -> inorder[8] = 4
    • 我们遍历 5，这时情况就不一样了。我们发现 index 恰好指向当前的栈顶节点 4，也就是说 4 没有右儿子，那么 5 必须为栈中某个节点的左儿子。那么如何找到这个节点呢？栈中的节点的顺序和它们在反向前序遍历中出现的顺序是一致的，而且每一个节点的左儿子都还没有被遍历过，那么这些节点的顺序和它们在反向中序遍历中出现的顺序一定是相反的。
      > 这是因为栈中的任意两个相邻的节点，前者都是后者的某个祖先。并且我们知道，栈中的任意一个节点的左儿子还没有被遍历过，说明后者一定是前者右儿子的子树中的节点，那么后者就先于前者出现在反向中序遍历中。
  • 因此我们可以把 index 不断向左移动，并与栈顶节点进行比较。如果 index 对应的元素恰好等于栈顶节点，那么说明我们在反向中序遍历中找到了栈顶节点，所以将 index 减少 1 并弹出栈顶节点，直到 index 对应的元素不等于栈顶节点。按照这样的过程，我们弹出的最后一个节点 x 就是 5 的双亲节点，这是因为 5 出现在了 x 与 x 在栈中的下一个节点的反向中序遍历之间，因此 5 就是 x 的左儿子。
  • 回到我们的例子，我们会依次从栈顶弹出 4，8 和 7，并且将 index 向左移动了三次。我们将 5 作为最后弹出的节点 7 的左儿子，并将 5 入栈。
    stack = [3, 20, 5]
    index -> inorder[5] = 5
  • 我们遍历 9。同理，index 恰好指向当前栈顶节点 5，那么我们会依次从栈顶弹出 5，20 和 3，并且将 index 向左移动了三次。我们将 9 作为最后弹出的节点 3 的左儿子，并将 9 入栈。
    stack = [9]
    index -> inorder[2] = 10
  • 我们遍历 10，将 10 作为栈顶节点 9 的右儿子，并将 10 入栈。
    stack = [9, 10]
    index -> inorder[2] = 10
  • 我们遍历 15。index 恰好指向当前栈顶节点 10，那么我们会依次从栈顶弹出 10 和 9，并且将 index 向左移动了两次。我们将 15 作为最后弹出的节点 9 的左儿子，并将 15 入栈。
    stack = [15]
    index -> inorder[0] = 15
  • 此时遍历结束，我们就构造出了正确的二叉树。

算法

  • 我们归纳出上述例子中的算法流程：
    • 我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（后序遍历的最后一个节点），指针指向中序遍历的最后一个节点；
    • 我们依次枚举后序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向左移动 index，并将当前节点作为最后一个弹出的节点的左儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的右儿子；
  • 无论是哪一种情况，我们最后都将当前的节点入栈。
  • 最后得到的二叉树即为答案。

复杂度分析：

  1. 时间复杂度:O(n)。其中 n 是树中的节点个数。

  2. 空间复杂度：O(n)。我们需要使用 O(n) 的空间存储哈希表，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h，所以总空间复杂度为 O(n)。

编码实现

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

精彩评论

跳转地址1：图解构造二叉树之中序+后序

思路：

  • 解决此问题的关键在于要很熟悉树的各种遍历次序代表的什么，最好能够将图画出来。本题解带你先进行中序遍历和后续遍历二叉树，然后再根据遍历结果将二叉树进行还原。
首先，来一棵树


– 查看树的遍历结果

  • 根据中序和后序遍历结果还原二叉树
    • 中序遍历和后续遍历的特性。首先来看题目给出的两个已知条件中序遍历序列和后序遍历序列 根据这两种遍历的特性我们可以得出两个结论
      • 在后序遍历序列中,最后一个元素为树的根节点
      • 在中序遍历序列中,根节点的左边为左子树，根节点的右边为右子树
    • 如下图所示
树的还原过程描述
  • 根据中序遍历和后续遍历的特性我们进行树的还原过程分析
    • 首先在后序遍历序列中找到根节点(最后一个元素)
    • 根据根节点在中序遍历序列中找到根节点的位置
    • 根据根节点的位置将中序遍历序列分为左子树和右子树
    • 根据根节点的位置确定左子树和右子树在中序数组和后续数组中的左右边界位置
    • 递归构造左子树和右子树
    • 返回根节点结束
树的还原过程变量定义
  • 需要定义几个变量帮助我们进行树的还原
    • HashMap memo 需要一个哈希表来保存中序遍历序列中,元素和索引的位置关系.因为从后序序列中拿到根节点后，要在中序序列中查找对应的位置,从而将数组分为左子树和右子树
    • int ri 根节点在中序遍历数组中的索引位置
    • 中序遍历数组的两个位置标记 [is, ie],is是起始位置，ie是结束位置
    • 后序遍历数组的两个位置标记 [ps, pe] ps是起始位置，pe是结束位置
位置关系的计算
  • 在找到根节点位置以后，我们要确定下一轮中，左子树和右子树在中序数组和后续数组中的左右边界的位置。
    • 左子树-中序数组 is = is, ie = ri – 1
    • 左子树-后序数组 ps = ps, pe = ps + ri – is – 1 (pe计算过程解释，后续数组的起始位置加上左子树长度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树)
    • 右子树-中序数组 is = ri + 1, ie = ie
    • 右子树-后序数组 ps = ps + ri – is, pe – 1
  • 听不明白没关系，看图就对了,计算图示如下
树的还原过程

编码实现

 class Solution {

    HashMap<Integer,Integer> memo = new HashMap<>();
    int[] post;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i = 0;i < inorder.length; i++) memo.put(inorder[i], i);
        post = postorder;
        TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1);
        return root;
    }

    public TreeNode buildTree(int is, int ie, int ps, int pe) {
        if(ie < is || pe < ps) return null;

        int root = post[pe];
        int ri = memo.get(root);

        TreeNode node = new TreeNode(root);
        node.left = buildTree(is, ri - 1, ps, ps + ri - is - 1);
        node.right = buildTree(ri + 1, ie, ps + ri - is, pe - 1);
        return node;
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

4 × 1 =