Reference: LeetCode Difficulty: Easy

Problem
Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are `structurally identical`

and the nodes have the `same value`

.

Example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Input: 1 1 / \ / \ 2 3 2 3 [1 ,2 ,3 ], [1 ,2 ,3 ] Output: true Input: 1 1 / \ 2 2 [1 ,2 ], [1 ,null ,2 ] Output: false

Analysis Recursion Note: Do the `null check`

at the beginning.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 public boolean isSameTree (TreeNode p, TreeNode q) { return preorder(p, q); } private boolean preorder (TreeNode p, TreeNode q) { if (p == null || q == null ) { return p == null && q == null ; } if (p.val != q.val) return false ; return preorder(p.left, q.left) && preorder(p.right, q.right); }

Time: $O(N)$Space: $O(h)$

Iteration Use two stacks to simulate the preorder traversal.

Note:

`Stack`

and `Queue`

can contain `null`

elements, while `Deque`

canâ€™t.
Do `null check`

first, and then do the `value check`

. Make sure `p`

and `q`

are not `null`

.
The `while condition`

should consider two stacks at the same time.
The `return`

statement should check if two stacks are empty at the same time.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public boolean isSameTree (TreeNode p, TreeNode q) { Stack<TreeNode> pStack = new Stack <>(); Stack<TreeNode> qStack = new Stack <>(); pStack.push(p); qStack.push(q); while (pStack.size() > 0 && qStack.size() > 0 ) { p = pStack.pop(); q = qStack.pop(); if (p == null || q == null ) { if (p == null && q == null ) continue ; else return false ; } if (p.val != q.val) return false ; pStack.push(p.right); qStack.push(q.right); pStack.push(p.left); qStack.push(q.left); } return pStack.size() == 0 && qStack.size() == 0 ; }

Time: $O(N)$Space: $O(h)$