construct-binary-tree-from-inorder-and-postorder-traversal

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given two integer arrays <code>inorder</code> and <code>postorder</code> where <code>inorder</code> is the inorder traversal of a binary tree and <code>postorder</code> is the postorder traversal of the same tree, construct and return the binary tree.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/tree.jpg" style="width: 277px; height: 302px;" />
<pre>
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
</pre>

Example 2:

<pre>
Input: inorder = [-1], postorder = [-1]
Output: [-1]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= inorder.length &lt;= 3000</code></li>
	<li><code>postorder.length == inorder.length</code></li>
	<li><code>-3000 &lt;= inorder[i], postorder[i] &lt;= 3000</code></li>
	<li><code>inorder</code> and <code>postorder</code> consist of unique values.</li>
	<li>Each value of <code>postorder</code> also appears in <code>inorder</code>.</li>
	<li><code>inorder</code> is guaranteed to be the inorder traversal of the tree.</li>
	<li><code>postorder</code> is guaranteed to be the postorder traversal of the tree.</li>
</ul>

buildTree

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

construct-binary-tree-from-preorder-and-inorder-traversal

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

Tree

Array

Hash Table

Divide and Conquer

Binary Tree

给定两个整数数组 <code>inorder</code> 和 <code>postorder</code> ，其中 <code>inorder</code> 是二叉树的中序遍历， <code>postorder</code> 是同一棵树的后序遍历，请你构造并返回这颗&nbsp;二叉树&nbsp;。

&nbsp;

示例 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/tree.jpg" />
<pre>
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
</pre>

示例 2:

<pre>
输入：inorder = [-1], postorder = [-1]
输出：[-1]
</pre>

&nbsp;

提示:

<ul>
	<li><code>1 &lt;= inorder.length &lt;= 3000</code></li>
	<li><code>postorder.length == inorder.length</code></li>
	<li><code>-3000 &lt;= inorder[i], postorder[i] &lt;= 3000</code></li>
	<li><code>inorder</code>&nbsp;和&nbsp;<code>postorder</code>&nbsp;都由 不同 的值组成</li>
	<li><code>postorder</code>&nbsp;中每一个值都在&nbsp;<code>inorder</code>&nbsp;中</li>
	<li><code>inorder</code>&nbsp;保证是树的中序遍历</li>
	<li><code>postorder</code>&nbsp;保证是树的后序遍历</li>
</ul>