100. Same Tree (DFS) 20.3.14 Easy

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:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true
Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false
Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Solution no.1: ---------------------------------------------------- DFS
-------------------------------- Time complexity: O(N), where N is a number of nodes in the tree
-------------------------------- Space complexity: O(log(N)) in the best case of completely balanced tree 类似于二分（left and right）
-------------------------------- and O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.  
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p is None and q is None:          # 都走到了尽头
            return True
        elif p and q:
            return (p.val == q.val) and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) # 三者同时为True才为True
        else:                                # 两个节点中，一个为None，另一个不为None
            return False
        

Solution no.2: -------------------------------------------------- Iteration with Queue
----------------------------------------------------------------- O(n) T and S
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        queue = collections.deque()
        queue.append(p)
        queue.append(q)
        while queue:
            if len(queue) % 2 != 0:
                return False
            tree_1 = queue.popleft()
            tree_2 = queue.popleft()
            if not tree_1 and not tree_2:
                continue
            if not tree_1 or not tree_2:
                return False
            if tree_1.val != tree_2.val:
                return False
            queue.append(tree_1.left)                               # We must also append None into the queue
            queue.append(tree_2.left)                               # Otherwise, [1, null, 2] and [1, 2] will return True
            queue.append(tree_1.right)
            queue.append(tree_2.right)
        return True


Java Version:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}