Given the roots of two binary trees root and sub, return True if some node of root,
together with all of its descendants, forms a tree identical to sub. An empty sub is
always contained.
Examples
3 4
/ \ / \
4 5 1 2
/ \
1 2
Input: root = build_tree([3, 4, 5, 1, 2]), sub = build_tree([4, 1, 2])
Output: True
3 4
/ \ / \
4 5 1 2
/ \
1 2
/
0
Input: root = build_tree([3, 4, 5, 1, 2, None, None, None, None, 0]), sub = build_tree([4, 1, 2])
Output: False
Explanation: the node 4 has an extra descendant 0, so its subtree is not identical to sub.
Constraints
0 <= number of nodes in root <= 2000,0 <= number of nodes in sub <= 100-10**4 <= node.val <= 10**4- Target complexity: O(n * m) time is acceptable.
Goals
- Reuse an 'identical trees' helper at every candidate node
- Understand that a subtree includes all descendants of its root
- Handle the empty subtree