create-binary-tree-from-descriptions

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 2D integer array <code>descriptions</code> where <code>descriptions[i] = [parenti, childi, isLefti]</code> indicates that <code>parenti</code> is the parent of <code>childi</code> in a binary tree of unique values. Furthermore,

<ul>
	<li>If <code>isLefti == 1</code>, then <code>childi</code> is the left child of <code>parenti</code>.</li>
	<li>If <code>isLefti == 0</code>, then <code>childi</code> is the right child of <code>parenti</code>.</li>
</ul>

Construct the binary tree described by <code>descriptions</code> and return its root.

The test cases will be generated such that the binary tree is valid.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/09/example1drawio.png" style="width: 300px; height: 236px;" />
<pre>
Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.
The resulting binary tree is shown in the diagram.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/09/example2drawio.png" style="width: 131px; height: 300px;" />
<pre>
Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.
The resulting binary tree is shown in the diagram.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= descriptions.length &lt;= 104</code></li>
	<li><code>descriptions[i].length == 3</code></li>
	<li><code>1 &lt;= parenti, childi &lt;= 105</code></li>
	<li><code>0 &lt;= isLefti &lt;= 1</code></li>
	<li>The binary tree described by <code>descriptions</code> is valid.</li>
</ul>

createBinaryTree

Create Binary Tree From Descriptions

Convert Sorted List to Binary Search Tree

convert-sorted-list-to-binary-search-tree

有序链表转换二叉搜索树

Number Of Ways To Reconstruct A Tree

number-of-ways-to-reconstruct-a-tree

重构一棵树的方案数

Tree

Array

Hash Table

Binary Tree

给你一个二维整数数组 <code>descriptions</code> ，其中 <code>descriptions[i] = [parenti, childi, isLefti]</code> 表示 <code>parenti</code> 是 <code>childi</code> 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：

<ul>
	<li>如果 <code>isLefti == 1</code> ，那么 <code>childi</code> 就是 <code>parenti</code> 的左子节点。</li>
	<li>如果 <code>isLefti == 0</code> ，那么 <code>childi</code> 就是 <code>parenti</code> 的右子节点。</li>
</ul>

请你根据 <code>descriptions</code> 的描述来构造二叉树并返回其 根节点 。

测试用例会保证可以构造出 有效 的二叉树。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/02/09/example1drawio.png" style="width: 300px; height: 236px;" />

<pre>
输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
输出：[50,20,80,15,17,19]
解释：根节点是值为 50 的节点，因为它没有父节点。
结果二叉树如上图所示。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/02/09/example2drawio.png" style="width: 131px; height: 300px;" />

<pre>
输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
输出：[1,2,null,null,3,4]
解释：根节点是值为 1 的节点，因为它没有父节点。 
结果二叉树如上图所示。 </pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= descriptions.length &lt;= 104</code></li>
	<li><code>descriptions[i].length == 3</code></li>
	<li><code>1 &lt;= parenti, childi &lt;= 105</code></li>
	<li><code>0 &lt;= isLefti &lt;= 1</code></li>
	<li><code>descriptions</code> 所描述的二叉树是一棵有效二叉树</li>
</ul>