Problem: 106. 从中序与后序遍历序列构造二叉树

文章目录

• 题目描述
• 思路
• 复杂度
• Code

  题目描述

  思路

  具体思路参考：

  Problem: 力扣105. 从前序与中序遍历序列构造二叉树

  再后序遍历中：每次取int rootVal = postorder[postEnd];构造根节点；左子树的范围是build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1)；右子树范围为build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1)

  复杂度

  时间复杂度:

  O ( n ) O(n) O(n)；其中 n n n为树节点的个数

  空间复杂度:

  O ( h e i g h ) O(heigh) O(heigh)；其中 h e i g h t height height为树的高度

  Code

  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      Map valToIndex = new HashMap<>();
      public TreeNode buildTree(int[] inorder, int[] postorder) {
          for (int i = 0; i < inorder.length; ++i) {
              valToIndex.put(inorder[i], i);
          }
          return build(inorder, 0, inorder.length - 1,
                  postorder, 0, postorder.length - 1);
      }
      TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
          if (inStart > inEnd) {
              return null;
          }
          // The value of the  root node is the last element of the post-order traversal group
          int rootVal = postorder[postEnd];
          // rootVal traverses the index in the group in medium order
          int index = valToIndex.get(rootVal);
          // Number of nodes in the left subtree
          int leftSize = index - inStart;
          TreeNode root = new TreeNode(rootVal);
          root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);
          root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
          return root;
      }
  }