Leetcode - 대칭 트리(JavaScript 포함)
문제는 다음과 같습니다.
이 문제에서 우리는 이진 트리가 구조와 값에서 대칭인지 여부를 테스트해야 합니다. 그렇다면 질문은 언제 두 나무가 서로 거울 반사가 되는가입니다.
왼쪽 하위 트리가 오른쪽 하위 트리의 거울 반사면 트리는 대칭입니다. 트리 중간에 선을 그리면 트리가 자체적으로 접힐 수 있으며 해당 노드 값은 동일합니다.
이제 재귀적으로 해결하겠습니다.
1) 먼저 루트 노드를 확인합니다. null인 경우 추가 조치가 필요하지 않습니다. null이 아니면 재귀로 들어가 왼쪽 및 오른쪽 하위 트리를 모두 확인해야 합니다.
var isSymmetric = function(root) {
if (root == null) return true;
return isMirror(root.left, root.right);
};
2) 왼쪽 하위 트리와 오른쪽 하위 트리가 모두 null이면 대칭임을 의미합니다. 그 중 하나만 null이면 비대칭입니다.
var isSymmetric = function(root) {
if (root == null) return true;
return isMirror(root.left, root.right);
};
const isMirror = function(leftSub, rightSub) {
if (leftSub == null && rightSub == null) return true;
if (leftSub == null || rightSub == null) return false;
}
3) 둘 다 null이 아닌 경우 해당 값을 확인해야 합니다. 동일하다면 노드의 왼쪽과 오른쪽으로 재귀를 계속할 것입니다. 왼쪽 하위 트리의 왼쪽 노드가 오른쪽 하위 트리의 오른쪽 노드와 동일하고 왼쪽 하위 트리의 오른쪽 노드가 오른쪽 하위 트리의 왼쪽 노드와 동일한지 확인해야 합니다.
var isSymmetric = function(root) {
if (root == null) return true;
return isMirror(root.left, root.right);
};
const isMirror = function(leftSub, rightSub) {
if (leftSub == null && rightSub == null) return true;
if (leftSub == null || rightSub == null) return false;
return (leftSub.val === rightSub.val
&& isMirror(leftSub.left, rightSub.right)
&& isMirror(leftSub.right, rightSub.left))
}
Reference
이 문제에 관하여(Leetcode - 대칭 트리(JavaScript 포함)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/urfan/leetcode-symmetric-tree-with-javascript-3404텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)