100.md

100. Same Tree

Description

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Solution

Solution 1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Traverse the binary tree with Depth-First Search (DFS) algorithm (preorder)
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    "use strict";
    let result = true;
    function dfs(node1, node2) {
        if (node1 && node2) {
            if (node1.val !== node2.val) {
                result = false;
            }
            dfs(node1.left, node2.left);
            dfs(node1.right, node2.right);
        } else if (node1 || node2) {
            result = false;
        }
    }
    dfs(p, q);
    return result;
};

Solution 2

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Traverse the binary tree with Depth-First Search (DFS) algorithm (preorder)
 * non-recursive
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    "use strict";
    if (p && q) {
        let stackP = [p], stackQ = [q];
        let pPtr = null, qPtr = null;
        while (stackP.length && stackQ.length) {
            pPtr = stackP.pop(), qPtr = stackQ.pop();
            if (pPtr && qPtr) {
                if (pPtr.val !== qPtr.val) {
                    return false;
                }
                stackP.push(pPtr.right);
                stackQ.push(qPtr.right);
                stackP.push(pPtr.left);
                stackQ.push(qPtr.left);
            } else {
                if (pPtr || qPtr) {
                    return false;
                }
            }
        }
        return true;
    }
    return p === q ? true : false;
};

Solution 3

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Traverse the binary tree with Breadth-First Search (BFS) algorithm
 * non-recursive
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    "use strict";
    if (p && q) {
        let queue1 = [p], queue2 = [q];
        while (queue1.length && queue2.length) {
            let len1 = queue1.length, len2 = queue2.length;
            if (len1 !== len2) {
                return false;
            }
            for (let i = 0; i < len1; i++) {
                if (queue1[i] && queue2[i]) {
                    if (queue1[i].val !== queue2[i].val) {
                        return false;
                    }
                    queue1.push(queue1[i].left);
                    queue1.push(queue1[i].right);
                    queue2.push(queue2[i].left);
                    queue2.push(queue2[i].right);
                } else if (queue1[i] || queue2[i]) {
                    return false;
                }
            }
            queue1 = queue1.slice(len1);
            queue2 = queue2.slice(len2);
        }
        return queue1.length === queue2.length ? true : false;
    }
    return p === q ? true : false;
};