2023-05-03：给你一棵 二叉树 的根节点 root ，树中有 n 个节点
每个节点都可以被分配一个从 1 到 n 且互不相同的值
另给你一个长度为 m 的数组 queries
你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作：
从树中 移除 以 queries[i] 的值作为根节点的子树
题目所用测试用例保证 queries[i] 不 等于根节点的值。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是执行第 i 个查询后树的高度。
注意：
查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。
树的高度是从根到树中某个节点的 最长简单路径中的边数 。
输入：root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]。
输出：[3,2,3,2]。
答案 2023-05-03：
大体过程：
1.定义和初始化全局变量
2.定义深度优先搜索函数 dfs
用一个计数器 i 记录当前节点的编号，并将其存储到数组 dfn 中。
将当前节点的深度 h 存储到数组 deep 中。
将当前节点的子树大小初始化为 1，存储到数组 size 中。
如果当前节点存在左孩子，则递归调用 dfs 函数，并将当前节点的子树大小加上其左孩子的子树大小。
如果当前节点存在右孩子，则递归调用 dfs 函数，并将当前节点的子树大小加上其右孩子的子树大小。
3.在主函数中创建一棵二叉树 root 和一个查询数组 queries。
4.对于每个查询 queries[i]，执行以下操作：
计算以 queries[i] 为根节点的子树编号范围，即 dfn[queries[i]] 到 dfn[queries[i]]+size[dfn[queries[i]]]-1。
将该范围内所有节点的深度保存到数组 maxl 中，并计算其前缀最大值。
将该范围内所有节点的深度保存到数组 maxr 中，并计算其后缀最大值。
计算左右子树的最大深度，取其中的较大值作为删除子树后树的高度。
将结果保存到答案数组 ans 中。
5.返回答案数组。
注意：在每次查询中，需要重新计算左右子树的最大深度，因为每次查询都会修改树的结构。
时间复杂度：
在 dfs 函数中，对于每个节点最多访问一次，因此该函数的时间复杂度为 O(n)，其中 n 是二叉树的节点数。
在 treeQueries 函数中，需要处理 m 个查询，对于每个查询需要计算左右子树的最大深度，时间复杂度为 O(n)，因此总时间复杂度为 O(mn)。
空间复杂度：
在 C++ 中，数组和变量的空间占用量是固定的，因此空间复杂度主要取决于递归调用时堆栈的空间占用量。由于最坏情况下二叉树可能退化成一个链表，因此堆栈空间的最大使用量为 O(n)，其中 n 是二叉树的节点数。
除了堆栈空间之外，还需要使用常量大小的额外空间来存储全局变量和临时变量，因此总空间复杂度为 O(n)。
go 完整代码如下：
package main
import ( "fmt")
type TreeNode struct { Val int Left *TreeNode Right *TreeNode}
const MAXN = 100010
var dfn [MAXN]intvar deep [MAXN]intvar size [MAXN]intvar maxl [MAXN]intvar maxr [MAXN]intvar n int
func treeQueries(root *TreeNode, queries []int) []int { n = 0 dfs(root, 0) for i := 1; i <= n; i++ { maxl[i] = max(maxl[i-1], deep[i]) } maxr[n+1] = 0 for i := n; i >= 1; i-- { maxr[i] = max(maxr[i+1], deep[i]) } m := len(queries) ans := make([]int, m) for i := 0; i < m; i++ { leftMax := maxl[dfn[queries[i]]-1] rightMax := maxr[dfn[queries[i]]+size[dfn[queries[i]]]] ans[i] = max(leftMax, rightMax) } return ans}
func dfs(head *TreeNode, h int) { i := n + 1 dfn[head.Val] = i deep[i] = h size[i] = 1 n = i if head.Left != nil { dfs(head.Left, h+1) size[i] += size[dfn[head.Left.Val]] } if head.Right != nil { dfs(head.Right, h+1) size[i] += size[dfn[head.Right.Val]] }}
func max(a, b int) int { if a > b { return a } return b}
func main() { root := &TreeNode{ Val: 5, Left: &TreeNode{ Val: 8, Left: &TreeNode{ Val: 2, Left: nil, Right: nil, }, Right: &TreeNode{ Val: 9, Left: nil, Right: nil, }, }, Right: &TreeNode{ Val: 3, Left: &TreeNode{ Val: 1, Left: nil, Right: nil, }, Right: &TreeNode{ Val: 7, Left: &TreeNode{ Val: 4, Left: nil, Right: nil, }, Right: &TreeNode{ Val: 6, Left: nil, Right: nil, }, }, }, } queries := []int{3, 2, 4, 8} ans := treeQueries(root, queries) fmt.Println("The query results are:", ans)}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <string.h>
#define MAXN 100010
struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right;};
int dfn[MAXN];int deep[MAXN];int size[MAXN];int maxl[MAXN];int maxr[MAXN];int n;
int max0(int a, int b) { return a > b ? a : b;}
void dfs(struct TreeNode* head, int h);int* treeQueries(struct TreeNode* root, int* queries, int queriesSize, int* returnSize);
int main() { struct TreeNode node9 = { 9, NULL, NULL }; struct TreeNode node8 = { 8, NULL, &node9 }; struct TreeNode node2 = { 2, NULL, NULL }; struct TreeNode node4 = { 4, NULL, NULL }; struct TreeNode node1 = { 1, NULL, NULL }; struct TreeNode node6 = { 6, NULL, NULL }; struct TreeNode node7 = { 7, &node4, &node6 }; struct TreeNode node3 = { 3, &node1, &node7 }; struct TreeNode node5 = { 5, &node8, &node3 }; struct TreeNode* root = &node5; int queries[] = { 3, 2, 4, 8 }; int queriesSize = sizeof(queries) / sizeof(int); int returnSize = 0; int* ans = treeQueries(root, queries, queriesSize, &returnSize); printf("The query results are: ["); for (int i = 0; i < returnSize; i++) { if (i > 0) { printf(", "); } printf("%d", ans[i]); } printf("]\n"); free(ans); return 0;}
void dfs(struct TreeNode* head, int h) { int i = ++n; dfn[head->val] = i; deep[i] = h; size[i] = 1; if (head->left != NULL) { dfs(head->left, h + 1); size[i] += size[dfn[head->left->val]]; } if (head->right != NULL) { dfs(head->right, h + 1); size[i] += size[dfn[head->right->val]]; }}
int* treeQueries(struct TreeNode* root, int* queries, int queriesSize, int* returnSize) { n = 0; dfs(root, 0); int i; for (i = 1; i <= n; i++) { maxl[i] = max0(maxl[i - 1], deep[i]); } maxr[n + 1] = 0; for (i = n; i >= 1; i--) { maxr[i] = max0(maxr[i + 1], deep[i]); } int* ans = (int*)malloc(queriesSize * sizeof(int)); for (i = 0; i < queriesSize; i++) { int leftMax = maxl[dfn[queries[i]] - 1]; int rightMax = maxr[dfn[queries[i]] + size[dfn[queries[i]]]]; ans[i] = max0(leftMax, rightMax); } *returnSize = queriesSize; return ans;}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>
using namespace std;
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};
const int MAXN = 100010;int dfn[MAXN];int deep[MAXN];int size0[MAXN];int maxl[MAXN];int maxr[MAXN];int n;
void dfs(TreeNode* head, int h) { int i = ++n; dfn[head->val] = i; deep[i] = h; size0[i] = 1; if (head->left != nullptr) { dfs(head->left, h + 1); size0[i] += size0[dfn[head->left->val]]; } if (head->right != nullptr) { dfs(head->right, h + 1); size0[i] += size0[dfn[head->right->val]]; }}
vector<int> treeQueries(TreeNode* root, vector<int>& queries) { n = 0; dfs(root, 0); for (int i = 1; i <= n; i++) { maxl[i] = max(maxl[i - 1], deep[i]); } maxr[n + 1] = 0; for (int i = n; i >= 1; i--) { maxr[i] = max(maxr[i + 1], deep[i]); } int m = (int)queries.size(); vector<int> ans(m); for (int i = 0; i < m; i++) { int leftMax = maxl[dfn[queries[i]] - 1]; int rightMax = maxr[dfn[queries[i]] + size0[dfn[queries[i]]]]; ans[i] = max(leftMax, rightMax); } return ans;}
int main() { TreeNode node9(9); TreeNode node8(8); node8.right = &node9; TreeNode node2(2); TreeNode node4(4); TreeNode node1(1); TreeNode node6(6); TreeNode node7(7); node7.left = &node4; node7.right = &node6; TreeNode node3(3); node3.left = &node1; node3.right = &node7; TreeNode node5(5); node5.left = &node8; node5.right = &node3; vector<int> queries{ 3, 2, 4, 8 }; auto ans = treeQueries(&node5, queries); cout << "The query results are: ["; for (int i = 0; i < ans.size(); i++) { if (i > 0) { cout << ", "; } cout << ans[i]; } cout << "]" << endl; return 0;}
复制代码
评论