솔루션 개발:

질문

Given the roots of two binary trees p and q, 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.

     1      1
    / \    / \
   2   3  2   3

Input: p = [1,2,3], q = [1,2,3]
Output: true

질문 설명

권장 지식

우리는 무엇을 알고 있습니까?

어떻게 할 것인가:

빅오 표기법:

리트코드 결과:

해결책

/**
 * 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) {
    /* -------------------------------------------------------------------------- */
    /*                               100. Same Tree                               */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */


    /* ----------------------------- Solution Below ----------------------------- */

    // So both our trees current node is null
    // This mean's they both reached the end of the tree
    // at the same time without error
    if (p == null && q == null) {
        return true;
    }

    // One of the pointers are null when another is not
    // This mean's one of our pointers has traversed to a correct node
    // but another has reached the end of the list too early and thus
    // cannot be a valid mirror tree
    if ((p == null && q != null) || (q == null && p != null)) {
        return false;
    }

    // As we have moved nodes
    // Are they the same value?
    if (p.val != q.val) {
        return false;
    }

    // Get both left nodes
    // We will traverse the left nodes in a DFS fashion
    // to be able to compare both left nodes at the same time
    // So we move left at the same time on both trees.
    let good_lefts = isSameTree(p.left, q.left);

    // Get both right nodes
    // We will traverse the right nodes in a DFS fashion
    // to be able to compare both right nodes at the same time
    // So we move right at the same time on both trees.
    let good_rights = isSameTree(p.right, q.right);

    // So are both sides good?
    return good_lefts && good_rights;
};