100. Same Tree

Same Tree - LeetCodeLeetCode

dfs

time: O(n)

space: O(h), worst O(n)

var isSameTree = function(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val !== q.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

iteration

time: O(n)

space: O(n), max(p, q) the number of nodes

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    
    let pq = [p];
    let qq = [q];

    while (pq.length > 0 && qq.length > 0) {
        const currp = pq.shift()
        const currq = qq.shift();

        if (currp !== null && currq !== null) {
            if (currp.val !== currq.val) return false;
        } else if (currp === null && currq === null) {
            continue;
        } else {
            return false;
        }

        pq.push(currp.left);
        pq.push(currp.right);

        qq.push(currq.left);
        qq.push(currq.right);

    }

    return true;
};