Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2458.html
2458. Height of Binary Tree After Subtree Removal Queries
- Difficulty: Hard.
- Related Topics: Array, Tree, Depth-First Search, Breadth-First Search, Binary Tree.
- Similar Questions: Maximum Depth of Binary Tree.
Problem
You are given the root
of a binary tree with n
nodes. Each node is assigned a unique value from 1
to n
. You are also given an array queries
of size m
.
You have to perform m
independent queries on the tree where in the ith
query you do the following:
- Remove the subtree rooted at the node with the value
queries[i]
from the tree. It is guaranteed thatqueries[i]
will not be equal to the value of the root.
Return an array **answer
of size m
where answer[i]
is the height of the tree after performing the ith
query**.
Note:
-
The queries are independent, so the tree returns to its initial state after each query.
-
The height of a tree is the number of edges in the longest simple path from the root to some node in the tree.
Example 1:
Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
Output: [2]
Explanation: The diagram above shows the tree after removing the subtree rooted at node with value 4.
The height of the tree is 2 (The path 1 -> 3 -> 2).
Example 2:
Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
Output: [3,2,3,2]
Explanation: We have the following queries:
- Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 4).
- Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -> 8 -> 1).
- Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 6).
- Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -> 9 -> 3).
Constraints:
-
The number of nodes in the tree is
n
. -
2 <= n <= 105
-
1 <= Node.val <= n
-
All the values in the tree are unique.
-
m == queries.length
-
1 <= m <= min(n, 104)
-
1 <= queries[i] <= n
-
queries[i] != root.val
Solution (Java, C++, Python)
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map<TreeNode, Integer> d = new HashMap<>(); private int[] res; public int[] treeQueries(TreeNode root, int[] queries) { f(root); res = new int[d.size() + 1]; d.put(null, 0); dfs(root, -1, 0); int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { ans[i] = res[queries[i]]; } return ans; } private void dfs(TreeNode root, int depth, int rest) { if (root == null) { return; } ++depth; res[root.val] = rest; dfs(root.left, depth, Math.max(rest, depth + d.get(root.right))); dfs(root.right, depth, Math.max(rest, depth + d.get(root.left))); } private int f(TreeNode root) { if (root == null) { return 0; } int l = f(root.left), r = f(root.right); d.put(root, 1 + Math.max(l, r)); return d.get(root); } }
-
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> treeQueries(TreeNode* root, vector<int>& queries) { unordered_map<TreeNode*, int> d; function<int(TreeNode*)> f = [&](TreeNode* root) -> int { if (!root) return 0; int l = f(root->left), r = f(root->right); d[root] = 1 + max(l, r); return d[root]; }; f(root); vector<int> res(d.size() + 1); function<void(TreeNode*, int, int)> dfs = [&](TreeNode* root, int depth, int rest) { if (!root) return; ++depth; res[root->val] = rest; dfs(root->left, depth, max(rest, depth + d[root->right])); dfs(root->right, depth, max(rest, depth + d[root->left])); }; dfs(root, -1, 0); vector<int> ans; for (int v : queries) ans.emplace_back(res[v]); return ans; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]: def f(root): if root is None: return 0 l, r = f(root.left), f(root.right) d[root] = 1 + max(l, r) return d[root] def dfs(root, depth, rest): if root is None: return depth += 1 res[root.val] = rest dfs(root.left, depth, max(rest, depth + d[root.right])) dfs(root.right, depth, max(rest, depth + d[root.left])) d = defaultdict(int) f(root) res = [0] * (len(d) + 1) dfs(root, -1, 0) return [res[v] for v in queries]
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func treeQueries(root *TreeNode, queries []int) (ans []int) { d := map[*TreeNode]int{} var f func(*TreeNode) int f = func(root *TreeNode) int { if root == nil { return 0 } l, r := f(root.Left), f(root.Right) d[root] = 1 + max(l, r) return d[root] } f(root) res := make([]int, len(d)+1) var dfs func(*TreeNode, int, int) dfs = func(root *TreeNode, depth, rest int) { if root == nil { return } depth++ res[root.Val] = rest dfs(root.Left, depth, max(rest, depth+d[root.Right])) dfs(root.Right, depth, max(rest, depth+d[root.Left])) } dfs(root, -1, 0) for _, v := range queries { ans = append(ans, res[v]) } return } func max(a, b int) int { if a > b { return a } return b }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).