Solution
Approach 1: Recursion
Intuition
The simplest strategy here is to use recursion.
Check if p
and q
nodes are not None
, and their values are equal.
If all checks are OK, do the same for the child nodes
recursively.
Implementation
!?!../Documents/100_LIS.json:1000,373!?!
Complexity Analysis

Time complexity : , where N is a number of nodes in the tree, since one visits each node exactly once.

Space complexity : in the best case of completely balanced tree and in the worst case of completely unbalanced tree, to keep a recursion stack.
Approach 2: Iteration
Intuition
Start from the root and then at each iteration pop the current node out of the deque. Then do the same checks as in the approach 1 :

p
andp
are notNone
, 
p.val
is equal toq.val
,
and if checks are OK, push the child nodes.
Implementation
Complexity Analysis

Time complexity : since each node is visited exactly once.

Space complexity : in the best case of completely balanced tree and in the worst case of completely unbalanced tree, to keep a deque.