Published on

[LeetCode 100] Same Tree

Problem

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.

Example 1:

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

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4

Thoughts

  • We can travel both trees in the same way, if any of the node is null or the values are not the same, the tress are not the same

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    let res: boolean = true;
    
    const travel = (node1: TreeNode, node2: TreeNode) => {
        if(res === false) return
        if(node1 === null && node2 === null) return
        
        if(node1 === null || node2 === null || node1.val !== node2.val) {
            res = false
            return
        }
        
        travel(node1.left, node2.left)
        travel(node1.right, node2.right)
    }
    
    travel(p, q)
    
    return res;
};

Reference