면접 문제 66: 대칭적인 두 갈래 나무
두 갈래 나무가 대칭적인지 아닌지를 판단하는 함수를 실현하세요.만약 두 갈래 나무가 그의 거울과 같다면, 그것은 대칭적이다.
생각:
귀속으로 판단할 수 있다.
우선 뿌리 결점의 좌우 결점 left,right의 값이 같은지 아닌지를 판단하고 다음 단계를 진행한다.
left->left와right->right가 같은지, left->right와right->left가 같은지, 같은지 판단하면 left와right가 대칭적이며 다음 단계를 진행합니다.
left->left와right->right의 대칭 여부, left->right와right->left의 대칭 여부를 판단합니다.대칭적이면 자결점에 대해 계속 판단한다.
#include <iostream>
#include <vector>
using namespace std;
struct Node{
int val;
Node *left;
Node *right;
Node(int _val) :val(_val), left(NULL), right(NULL){}
};
bool IsSymmetricalNode(Node *n1, Node *n2)
{
if (n1 == NULL && n2 == NULL) return true;
else if (n1 == NULL || n2 == NULL) return false;
if (n1->val != n2->val) return false;
return IsSymmetricalNode(n1->left, n2->right) && IsSymmetricalNode(n1->right, n2->left);
}
bool IsSymmetricalTree(Node *root)
{
if (root == NULL) return true;
return IsSymmetricalNode(root->left, root->right);
}
int main()
{
Node *n1 = new Node(1);
Node *n2 = new Node(2);
Node *n3 = new Node(2);
Node *n4 = new Node(4);
Node *n5 = new Node(5);
Node *n6 = new Node(5);
Node *n7 = new Node(4);
Node *n8 = new Node(3);
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
n3->left = n6;
n3->right = n7;
n7->right = n8;
cout << IsSymmetricalTree(n1) << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.