← 返回 doordash 的题目列表Count Changed Nodes Between Two Menu Trees (Activation/Deactivation/Value Update)
类型：online_judge
Problem: Count Changed Nodes Between Two Menu Trees (Activation/Deactivation/Value Update)
A DoorDash menu can be modeled as a tree. Each node has:
key: a unique string identifier (unique within a tree)
value: an integer
children: a list of child nodes (order does not matter; matching is by key)
Given an existing menu tree and a new menu tree sent by a merchant, count how many nodes have changed.
A node (identified by key) is considered changed if:
Added: its key exists only in the new tree.
Deactivated: its key exists only in the existing tree (missing in the new tree). Deactivated nodes are counted as changes.
Updated: its key exists in both trees but value differs.
Return the total number of changed nodes (Added + Deactivated + Updated).
Notes:
Only node existence and value differences matter.
Children order does not matter; match by key.
If a node is deactivated, all nodes in its subtree are also deactivated and counted.
Constraints
Node counts N and M in the two trees: 1 <= N, M <= 2 * 10^5
Expected time: O(N + M)
Example 1
Existing:
a(1)
b(2)
d(4)
e(5)
c(3)
f(6)
New:
a(1)
c(3)
f(66)
Output: 4
Example 2
Existing:
a(1)
b(2)
d(4)
e(5)
c(3)
g(7)
New:
a(1)
b(2)
e(5)
d(4)
f(6)
h(8)
g(7)
Output: 5
Example
Input
Example1
(existing tree and new tree as described in prompt)
Output
4