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;
};
Reference
이 문제에 관하여(101. 대칭 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/cod3pineapple/101-symmetric-tree-2ijk텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)