2023-05-03：給你一棵 二叉樹 的根節(jié)點 root ，樹中有 n 個節(jié)點 每個節(jié)點都可以被分配
2023-05-03：給你一棵 二叉樹 的根節(jié)點 root ，樹中有 n 個節(jié)點
每個節(jié)點都可以被分配一個從 1 到 n 且互不相同的值
另給你一個長度為 m 的數組 queries
你必須在樹上執(zhí)行 m 個 獨立 的查詢，其中第 i 個查詢你需要執(zhí)行以下操作：
從樹中 移除 以 queries[i] 的值作為根節(jié)點的子樹
題目所用測試用例保證 queries[i] 不 等于根節(jié)點的值。
返回一個長度為 m 的數組 answer ，其中 answer[i] 是執(zhí)行第 i 個查詢后樹的高度。
注意：
查詢之間是獨立的，所以在每個查詢執(zhí)行后，樹會回到其 初始 狀態(tài)。
樹的高度是從根到樹中某個節(jié)點的 最長簡單路徑中的邊數 。
輸入：root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]。
輸出：[3,2,3,2]。
答案2023-05-03：
大體過程：
1.定義和初始化全局變量
??使用常量?
MAXN?定義數組大小。??定義用于深度優(yōu)先搜索的四個數組?
dfn、deep、size、maxl、maxr?和一個計數器?n，保存每個節(jié)點的編號、深度、子樹大小、左右子樹的最大深度。
2.定義深度優(yōu)先搜索函數?dfs
??用一個計數器?
i?記錄當前節(jié)點的編號，并將其存儲到數組?dfn?中。??將當前節(jié)點的深度?
h?存儲到數組?deep?中。??將當前節(jié)點的子樹大小初始化為 1，存儲到數組?
size?中。??如果當前節(jié)點存在左孩子，則遞歸調用?
dfs?函數，并將當前節(jié)點的子樹大小加上其左孩子的子樹大小。??如果當前節(jié)點存在右孩子，則遞歸調用?
dfs?函數，并將當前節(jié)點的子樹大小加上其右孩子的子樹大小。
3.在主函數中創(chuàng)建一棵二叉樹?root?和一個查詢數組?queries。
4.對于每個查詢?queries[i]，執(zhí)行以下操作：
??計算以?
queries[i]?為根節(jié)點的子樹編號范圍，即?dfn[queries[i]]?到?dfn[queries[i]]+size[dfn[queries[i]]]-1。??將該范圍內所有節(jié)點的深度保存到數組?
maxl?中，并計算其前綴最大值。??將該范圍內所有節(jié)點的深度保存到數組?
maxr?中，并計算其后綴最大值。??計算左右子樹的最大深度，取其中的較大值作為刪除子樹后樹的高度。
??將結果保存到答案數組?
ans?中。
5.返回答案數組。
注意：在每次查詢中，需要重新計算左右子樹的最大深度，因為每次查詢都會修改樹的結構。
時間復雜度：
在?dfs?函數中，對于每個節(jié)點最多訪問一次，因此該函數的時間復雜度為 O(n)，其中 n 是二叉樹的節(jié)點數。
在?treeQueries?函數中，需要處理 $m$ 個查詢，對于每個查詢需要計算左右子樹的最大深度，時間復雜度為 O(n)，因此總時間復雜度為 O(mn)。
空間復雜度：
在 C++ 中，數組和變量的空間占用量是固定的，因此空間復雜度主要取決于遞歸調用時堆棧的空間占用量。由于最壞情況下二叉樹可能退化成一個鏈表，因此堆?？臻g的最大使用量為 O(n)，其中 n 是二叉樹的節(jié)點數。
除了堆?？臻g之外，還需要使用常量大小的額外空間來存儲全局變量和臨時變量，因此總空間復雜度為 O(n)。
go完整代碼如下：
package?main
import?(
????"fmt"
)
type?TreeNode?struct?{
????Val???int
????Left??*TreeNode
????Right?*TreeNode
}
const?MAXN?=?100010
var?dfn?[MAXN]int
var?deep?[MAXN]int
var?size?[MAXN]int
var?maxl?[MAXN]int
var?maxr?[MAXN]int
var?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完整代碼如下：
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++完整代碼如下：
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;
}
