100. Same Tree

Recursion:

public boolean isSameTree(TreeNode left, TreeNode right) {
    if (p == null || q == null) return p == q; // combine two cases: (p == null && p == null) and (p == null || q == null)
    return left.val == right.val && 
        isSameTree(left.left, right.left) && isSameTree(left.right, right.right);
}

Iteration: 在loop中找不同, 只用一个queue

public boolean isSameTree(TreeNode p, TreeNode q) {
    LinkedList<TreeNode> l1 = new LinkedList<>();
    LinkedList<TreeNode> l2 = new LinkedList<>();

    l1.add(p);
    l2.add(q);

    while (!l1.isEmpty()) { 
        TreeNode node1 = l1.remove();
        TreeNode node2 = l2.remove();

        if (node1 == null && node2 == null) continue;
        if (node1 == null || node2 == null) return false;
        if (node1.val != node2.val) return false;

        l1.add(node1.left);
        l2.add(node2.left);

        l1.add(node1.right);
        l2.add(node2.right);
    }
    return true;
}

难点：两个不一样的queue或者stack检查null exception

考虑几种边界情况

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

注意一些api的用法，arraylist和linkedlist可以有null,但arraydeque不行

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false; // different from linedlist

    Deque<TreeNode> l1 = new ArrayDeque<>();
    Deque<TreeNode> l2 = new ArrayDeque<>();

    l1.add(p);
    l2.add(q);

    while (!l1.isEmpty()) { // l1 or l2 can't be null at first
        TreeNode node1 = l1.remove();
        TreeNode node2 = l2.remove();

        if (!check(node1, node2)) return false;

        if (!check(node1.left, node2.left)) return false; // check intermediate node
        if (node1.left != null) { // check leaf node
            l1.add(node1.left);
            l2.add(node2.left);
        }

        if (!check(node1.right, node2.right)) return false; // check intermediate node
        if (node2.right != null) { // check leaf node
            l1.add(node1.right);
            l2.add(node2.right);
        }
    }
    return true;
}

public boolean check(TreeNode p, TreeNode q) {
    if (p == null || q == null) return p == q;
    return p.val == q.val;
}