主題
題目連結：
題目意譯：
你被給定一棵有著 n 個節點的二元樹之根節點 root。每個節點都被指派一個介於 1 到 n 的數字，彼此相異。你同時也被給定一個大小為 m 的陣列 queries。
你需要執行 m 次在樹上彼此之間獨立的若干筆詢問，其中第 i 筆詢問你將做出以下動作：
從樹中將以節點值為 queries[i] 的節點作為根節點的子樹移除。保證 queries[i] 不會等於 root 的數值。
回傳一個大小為 m 的陣列 answer，其中 answer[i] 為執行第 i 筆詢問後樹的高度。
注：
每筆詢問之間彼此獨立，所以這棵樹將會在每筆詢問之後回到原始狀態。
一棵樹的高度為從根節點到某個節點之最長的簡單路徑上的邊數。
限制：
該樹的節點數為 n。
2 ≦ n ≦ 10 ^ 5
1 ≦ Node.val ≦ n
樹中的節點值彼此相異。
m == queries.length
1 ≦ m ≦ min(n, 10 ^ 4)
1 ≦ queries[i] ≦ n
queries[i] != root.val
範例測資：
範例 1：
輸入： root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
輸出： [2]
解釋： 上圖顯示移除以節點值為 4 的節點作為根節點的子樹之後的樹。
該樹的高度為 2（路徑 1 → 3 → 2）。
範例 2：
輸入： root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
輸出： [3,2,3,2]
解釋： 我們有以下詢問：
- 移除以節點值為 3 的節點作為根節點的子樹。樹的高度變為 3（路徑 5 → 8 → 2 → 4）。
- 移除以節點值為 2 的節點作為根節點的子樹。樹的高度變為 2（路徑 5 → 8 → 1）。
- 移除以節點值為 4 的節點作為根節點的子樹。樹的高度變為 3（路徑 5 → 8 → 2 → 6）。
- 移除以節點值為 8 的節點作為根節點的子樹。樹的高度變為 2（路徑 5 → 9 → 3）。
解題思維：
樹的高度和深度基本上求法一樣（參見這題），只是定義不同而已。
而現在我們想要知道對於每一個子樹，其移除之後剩餘樹之高度（即所求）。如該子樹為某個節點 X 的左子樹，則剩餘樹的高度之資訊將會從 X 的父母節點以及 X 的右子樹來；相似地，若該子樹為 X 的右子樹，則所求高度之資訊將從 X 的父母節點以及 X 的左子樹傳過來。
因此，我們可以把深度優先搜尋（Depth First Search，DFS）求高度的遞迴式拆成兩種，一種是統一先往左子樹遞迴並將高度結果往右子樹傳（對應到上面的第二種情況，不過）、另一種則是統一先往右子樹遞迴並將高度結果往左子樹傳（對應到上述第一種情況）。
然後在過程中用一個陣列來記錄每一個節點的所求高度值。最後掃過一遍 queries 然後根據此陣列把對應的結果塞進 answer 裡面並回傳即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
