height-of-binary-tree-after-subtree-removal-queries

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 the <code>root</code> of a binary tree with <code>n</code> nodes. Each node is assigned a unique value from <code>1</code> to <code>n</code>. You are also given an array <code>queries</code> of size <code>m</code>.

You have to perform <code>m</code> independent queries on the tree where in the <code>ith</code> query you do the following:

<ul>
	<li>Remove the subtree rooted at the node with the value <code>queries[i]</code> from the tree. It is guaranteed that <code>queries[i]</code> will not be equal to the value of the root.</li>
</ul>

Return an array <code>answer</code> of size <code>m</code> where <code>answer[i]</code> is the height of the tree after performing the <code>ith</code> query.

Note:

<ul>
	<li>The queries are independent, so the tree returns to its initial state after each query.</li>
	<li>The height of a tree is the number of edges in the longest simple path from the root to some node in the tree.</li>
</ul>

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-1.png" style="width: 495px; height: 281px;" />
<pre>
Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
Output: [2]
Explanation: The diagram above shows the tree after removing the subtree rooted at node with value 4.
The height of the tree is 2 (The path 1 -&gt; 3 -&gt; 2).
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-2.png" style="width: 301px; height: 284px;" />
<pre>
Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
Output: [3,2,3,2]
Explanation: We have the following queries:
- Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -&gt; 8 -&gt; 2 -&gt; 4).
- Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -&gt; 8 -&gt; 1).
- Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -&gt; 8 -&gt; 2 -&gt; 6).
- Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -&gt; 9 -&gt; 3).
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= Node.val &lt;= n</code></li>
	<li>All the values in the tree are unique.</li>
	<li><code>m == queries.length</code></li>
	<li><code>1 &lt;= m &lt;= min(n, 104)</code></li>
	<li><code>1 &lt;= queries[i] &lt;= n</code></li>
	<li><code>queries[i] != root.val</code></li>
</ul>

treeQueries

Height of Binary Tree After Subtree Removal Queries

Maximum Depth of Binary Tree

maximum-depth-of-binary-tree

二叉树的最大深度

Tree

Depth-First Search

Breadth-First Search

Array

Binary Tree

给你一棵 二叉树 的根节点 <code>root</code> ，树中有 <code>n</code> 个节点。每个节点都可以被分配一个从 <code>1</code> 到 <code>n</code> 且互不相同的值。另给你一个长度为 <code>m</code> 的数组 <code>queries</code> 。

你必须在树上执行 <code>m</code> 个 独立 的查询，其中第 <code>i</code> 个查询你需要执行以下操作：

<ul>
	<li>从树中 移除 以 <code>queries[i]</code> 的值作为根节点的子树。题目所用测试用例保证 <code>queries[i]</code> 不 等于根节点的值。</li>
</ul>

返回一个长度为 <code>m</code> 的数组 <code>answer</code> ，其中 <code>answer[i]</code> 是执行第 <code>i</code> 个查询后树的高度。

注意：

<ul>
	<li>查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。</li>
	<li>树的高度是从根到树中某个节点的 最长简单路径中的边数 。</li>
</ul>

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-1.png" style="width: 495px; height: 281px;" />

<pre>
输入：root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
输出：[2]
解释：上图展示了从树中移除以 4 为根节点的子树。
树的高度是 2（路径为 1 -&gt; 3 -&gt; 2）。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-2.png" style="width: 301px; height: 284px;" />

<pre>
输入：root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
输出：[3,2,3,2]
解释：执行下述查询：
- 移除以 3 为根节点的子树。树的高度变为 3（路径为 5 -&gt; 8 -&gt; 2 -&gt; 4）。
- 移除以 2 为根节点的子树。树的高度变为 2（路径为 5 -&gt; 8 -&gt; 1）。
- 移除以 4 为根节点的子树。树的高度变为 3（路径为 5 -&gt; 8 -&gt; 2 -&gt; 6）。
- 移除以 8 为根节点的子树。树的高度变为 2（路径为 5 -&gt; 9 -&gt; 3）。
</pre>

&nbsp;

提示：

<ul>
	<li>树中节点的数目是 <code>n</code></li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= Node.val &lt;= n</code></li>
	<li>树中的所有值 互不相同</li>
	<li><code>m == queries.length</code></li>
	<li><code>1 &lt;= m &lt;= min(n, 104)</code></li>
	<li><code>1 &lt;= queries[i] &lt;= n</code></li>
	<li><code>queries[i] != root.val</code></li>
</ul>