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

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 an array <code>pairs</code>, where <code>pairs[i] = [xi, yi]</code>, and:

<ul>
	<li>There are no duplicates.</li>
	<li><code>xi &lt; yi</code></li>
</ul>

Let <code>ways</code> be the number of rooted trees that satisfy the following conditions:

<ul>
	<li>The tree consists of nodes whose values appeared in <code>pairs</code>.</li>
	<li>A pair <code>[xi, yi]</code> exists in <code>pairs</code> if and only if <code>xi</code> is an ancestor of <code>yi</code> or <code>yi</code> is an ancestor of <code>xi</code>.</li>
	<li>Note: the tree does not have to be a binary tree.</li>
</ul>

Two ways are considered to be different if there is at least one node that has different parents in both ways.

Return:

<ul>
	<li><code>0</code> if <code>ways == 0</code></li>
	<li><code>1</code> if <code>ways == 1</code></li>
	<li><code>2</code> if <code>ways &gt; 1</code></li>
</ul>

A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

&nbsp;
Example 1:
<img src="https://assets.leetcode.com/uploads/2020/12/03/trees2.png" style="width: 208px; height: 221px;" />
<pre>
Input: pairs = [[1,2],[2,3]]
Output: 1
Explanation: There is exactly one valid rooted tree, which is shown in the above figure.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/03/tree.png" style="width: 234px; height: 241px;" />
<pre>
Input: pairs = [[1,2],[2,3],[1,3]]
Output: 2
Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.
</pre>

Example 3:

<pre>
Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
Output: 0
Explanation: There are no valid rooted trees.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= pairs.length &lt;= 105</code></li>
	<li><code>1 &lt;= xi &lt; yi &lt;= 500</code></li>
	<li>The elements in <code>pairs</code> are unique.</li>
</ul>

checkWays

Number Of Ways To Reconstruct A Tree

Create Binary Tree From Descriptions

create-binary-tree-from-descriptions

根据描述创建二叉树

Maximum Star Sum of a Graph

maximum-star-sum-of-a-graph

图中最大星和

Tree

Graph

给你一个数组 <code>pairs</code> ，其中 <code>pairs[i] = [xi, yi]</code> ，并且满足：

<ul>
	<li><code>pairs</code> 中没有重复元素</li>
	<li><code>xi < yi</code></li>
</ul>

令 <code>ways</code> 为满足下面条件的有根树的方案数：

<ul>
	<li>树所包含的所有节点值都在 <code>pairs</code> 中。</li>
	<li>一个数对 <code>[xi, yi]</code> 出现在 <code>pairs</code> 中 当且仅当 <code>xi</code> 是 <code>yi</code> 的祖先或者 <code>yi</code> 是 <code>xi</code> 的祖先。</li>
	<li>注意：构造出来的树不一定是二叉树。</li>
</ul>

两棵树被视为不同的方案当存在至少一个节点在两棵树中有不同的父节点。

请你返回：

<ul>
	<li>如果 <code>ways == 0</code> ，返回 <code>0</code> 。</li>
	<li>如果 <code>ways == 1</code> ，返回 <code>1</code> 。</li>
	<li>如果 <code>ways > 1</code> ，返回 <code>2</code> 。</li>
</ul>

一棵 有根树 指的是只有一个根节点的树，所有边都是从根往外的方向。

我们称从根到一个节点路径上的任意一个节点（除去节点本身）都是该节点的 祖先 。根节点没有祖先。

 

示例 1：
<img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/09/trees2.png" style="width: 208px; height: 221px;" />
<pre>
输入：pairs = [[1,2],[2,3]]
输出：1
解释：如上图所示，有且只有一个符合规定的有根树。
</pre>

示例 2：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/09/tree.png" style="width: 234px; height: 241px;" />
<pre>
输入：pairs = [[1,2],[2,3],[1,3]]
输出：2
解释：有多个符合规定的有根树，其中三个如上图所示。
</pre>

示例 3：

<pre>
输入：pairs = [[1,2],[2,3],[2,4],[1,5]]
输出：0
解释：没有符合规定的有根树。</pre>

 

提示：

<ul>
	<li><code>1 <= pairs.length <= 105</code></li>
	<li><code>1 <= xi < yi <= 500</code></li>
	<li><code>pairs</code> 中的元素互不相同。</li>
</ul>