Re: [閒聊] 每日leetcode

[dont (dont)]

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