题目地址(106. 从中序与后序遍历序列构造二叉树)

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

题目描述

  1. 根据一棵树的中序遍历与后序遍历构造二叉树。
  3. 注意:
  4. 你可以假设树中没有重复的元素。
  6. 例如，给出
  8. 中序遍历 inorder = [9,3,15,20,7]
  9. 后序遍历 postorder = [9,15,7,20,3]
  11. 返回如下的二叉树：
  13.     3
  14.    / \
  15.   9  20
  16.     /  \
  17.    15   7

前置知识


公司

  • 暂无

思路

image.png

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public TreeNode buildTree(int[] inorder, int[] postorder) {
  19.             return loop(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
  20.         }
  22.         public TreeNode loop(int[] inorder, int inLeft, int inRight,
  23.                              int[] postorder, int postLeft, int postRight) {
  24.             //如果中序序列为空的话 就返回null
  25.             if (inRight < inLeft ) {
  26.                 return null;
  27.             }
  28.             //找出根节点 也就是后序序列里的最后一个数
  29.             int rootVal = postorder[postRight];
  30.             TreeNode root = new TreeNode(rootVal);
  31.             //将根节点的位置 在中序序列里找出
  32.             int index = 0;
  33.             for (int i = inLeft; i <= inRight; i++) {
  34.                 if (inorder[i] == rootVal) {
  35.                     index = i;
  36.                     break;
  37.                 }
  38.             }
  39.             //对序列分别进行拆分
  40.             //左子树
  41.             int leftSize = index - inLeft;
  42.             root.left = loop(inorder, inLeft, index -1,
  43.                              postorder, postLeft, postLeft + leftSize -1);
  44.             //右子树
  45.             root.right = loop(inorder, index + 1, inRight,
  46.                               postorder, postLeft + leftSize, postRight - 1);
  47.             return root;
  48.         }
  49.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：106. 从中序与后序遍历序列构造二叉树 - 图2#card=math&code=O%28n%29&id=zK8hd)
  • 空间复杂度：106. 从中序与后序遍历序列构造二叉树 - 图3#card=math&code=O%28n%29&id=DTsoH)