101. 대칭 트리

설명:



이진 트리가 주어지면 그것이 자신의 거울인지(즉, 중심을 중심으로 대칭인지) 확인하십시오.

해결책:



시간 복잡도 : O(n)
공간 복잡도: O(n)

// Recursive solution
// Look at both children at the same time and check if they are a mirror image
var isSymmetric = function(left, right = left) {
    // Check for the base cases where a child is null or if both children are null
    if(left === null && right === null) return true;
    if(left === null || right === null) return false;
    // Check if the mirror node vals are the same
    // If they are then continue checking children nodes
    return left.val === right.val && isSymmetric(left.left, right.right) &&  isSymmetric(left.right, right.left);
};

// Iterative solution
// Breadth first search approach
// Push in child nodes in mirror order
// Make sure each mirror node val is equivalent
var isSymmetric = function(root) {
    // Create the queue and add root node twice
    // Each instance reference represents one side of the tree
    const q = [];
    q.push(root);
    q.push(root);
    while(q.length) {
        // Get the current nodes to check
        const left = q.pop();
        const right = q.pop();
        // Use the same logic in the recursive solution
        if(left === null && right === null) continue;
        if(left === null || right === null) return false;
        if(left.val !== right.val) return false;
        q.push(left.left);
        q.push(right.right);
        q.push(left.right);
        q.push(right.left);
    }
    return true;
};

좋은 웹페이지 즐겨찾기