101. Symmetric Tree

Leetcode

https://leetcode.com/problems/symmetric-tree/

題目

Given the root of 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

解答

• 方法一

Recursion

var isSymmetric = function(root) {
    const isMirror = (node1, node2) => {
        if(node1 === null && node2 === null) return true;
        if(node1 === null || node2 === null) return false;
        return (node1.val === node2.val) 
            && isMirror(node1.left, node2.right)
            && isMirror(node1.right, node2.left)
    }
    
    return isMirror(root, root);
};

Runtime: 72 ms, faster than 90.41% of JavaScript online submissions for Symmetric Tree.

Memory Usage: 45.1 MB, less than 13.46% of JavaScript online submissions for Symmetric Tree.

• 方法二

Iteration

var isSymmetric = function(root) {
    const queue = [root, root];
    
    while(queue.length) {
        const node1 = queue.shift();
        const node2 = queue.shift();
        if (node1 === null && node2 === null) continue;
        if (node1 === null || node2 === null) return false;
        if (node1.val !== node2.val) return false;
        
        // 將相對稱的 node 依序放在 queue 的最前面
        queue.push(node1.left);
        queue.push(node2.right);
        queue.push(node1.right);
        queue.push(node2.left);
    }
    return true;
};

Runtime: 85 ms, faster than 71.63% of JavaScript online submissions for Symmetric Tree.

Memory Usage: 44.8 MB, less than 32.01% of JavaScript online submissions for Symmetric Tree.