[Leetcode] Symmetric Tree

101. Symmetric Tree

Given the rootof a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

The number of nodes in the tree is in the range [1, 1000].

-100 <= Node.val <= 100

how to understand?

Think of mirror. central node is the standard to compare. left tree and right tree should be same when it's mirrored. right node's left node should be same as left node's right node.

How to approach?

Recursive

function isSymmetric(root: TreeNode | null): boolean {
    return isMirror(root, root);
}
function isMirror(t1: TreeNode | null, t2: TreeNode | null): boolean {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    return (
        t1.val === t2.val &&
        isMirror(t1.right, t2.left) &&
        isMirror(t1.left, t2.right)
    );
}

create helper function isMirror

in the solution, return the isMirror with 2 root inputs.

2 if condition will check the each node is not null, when both are null it will return true. when one of them is null then it will return false since it's not symmetric.

finally return the 3 boolean conditions chained by &&

check the node value is same, and left isMirror, right isMirror result.

Iteration

function isSymmetric(root: TreeNode | null): boolean {
    let q: Array<TreeNode | null> = [root, root];
    while (q.length !== 0) {
        let t1: TreeNode | null = q.shift();
        let t2: TreeNode | null = q.shift();
        if (t1 === null && t2 === null) {
            continue;
        }
        if (t1 === null || t2 === null) {
            return false;
        }
        if (t1.val !== t2.val) {
            return false;
        }
        q.push(t1.left, t2.right, t1.right, t2.left);
    }
    return true;
}

create queue, initialise with 2 root nodes.

set while condition to check the length of the queue

get the first and second node in the queue and set it as t1 and t2

3 if conditions to check if the tree is symmetric

first it will check the both nodes are not null, continue to next condition

second it will check if one of them is null, return false.

third check the node value is same, if it is not same then return false.

lastly push the node's left and right value in order to compare if it's symmetric.

when there is nothing to compare then return true.

Summary

Recursive solution calls itself recursively until it reaches the base case in itself.

Iteration solution use queue to check the nodes in order.