Re: [閒聊] 每日leetcode
2458. Height of Binary Tree After Subtree Removal Queries
## 思路
DFS 記錄刪掉node之後的height
max(curr_max, depth + sibling height)
e.g.
1
2 3
4 5
6
刪掉3的高度 = 4 [1,2,5,6] -- depth + sibling子樹(2)的height
## Code
class Solution:
def treeQueries(self, root: Optional[TreeNode], queries: List[int]) ->
List[int]:
res = defaultdict(int)
@cache
def get_height(node):
if not node:
return -1
left = get_height(node.left)
right = get_height(node.right)
return 1 + max(left, right)
def dfs(node, depth, max_height):
if not node:
return
res[node.val] = max_height
dfs(node.left, depth+1, max(max_height, depth +
get_height(node.right)))
dfs(node.right, depth+1, max(max_height, depth +
get_height(node.left)))
dfs(root, 1, 0)
return [res[q] for q in queries]
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.44 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729908313.A.3F8.html
討論串 (同標題文章)
完整討論串 (本文為第 1050 之 1554 篇)：