면접 문제 66: 대칭적인 두 갈래 나무

1469 단어
제목:
두 갈래 나무가 대칭적인지 아닌지를 판단하는 함수를 실현하세요.만약 두 갈래 나무가 그의 거울과 같다면, 그것은 대칭적이다.
생각:
귀속으로 판단할 수 있다.
우선 뿌리 결점의 좌우 결점 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;
}

좋은 웹페이지 즐겨찾기