leetcode_101번 - Symmetric Tree(트리, 귀속, 그리고 반복해서 생각해 내지 못했다)

Symmetric Tree

 
Total Accepted: 52678 Total Submissions: 166910 My Submissions
Question
 Solution 
 
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

    1

   / \

  2   2

 / \ / \

3  4 4  3

 
But the following is not:

    1

   / \

  2   2

   \   \

   3    3

 
Note:Bonus points if you could solve it both recursively and iteratively.
confused what  "{1,#,2,3}"  means?  > read more on how binary tree is serialized on OJ.
 
Hide Tags
 
Tree   Depth-first Search
Have you met this question in a real interview? 
Yes
 
No
 
Discuss
이 문제는 뿌리 결점의 두 좌우 나무를 각각 차례대로 훑어본 다음에 얻은 결과를 수조에 저장하고 그 다음에 비교하여 서로 같은지 아닌지를 보려는 것이다. 그러나 이렇게 하면
질문이 하나 있습니다. 하나, 둘, 둘, 셋, 셋, 셋. 이런 상황에서 그는 비대칭적이지만 내 방식대로라면 똑같습니다.

#include<iostream>

#include<stack>

#include <vector>

using namespace std;





 // Definition for binary tree

struct TreeNode {

      int val;

      TreeNode *left;

      TreeNode *right;

      TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};



// 

void first_search(TreeNode* root,vector<int>& temp)

{

	if(root==NULL)

		return;

	temp.push_back(root->val);

	if(root->left!=NULL)

		first_search(root->left,temp);

	else

		temp.push_back('#');

	if(root->right!=NULL)

		first_search(root->right,temp);

	else

		temp.push_back('#');

	return;

}

bool isSymmetric(TreeNode *root) {

	if(root==NULL)

		return 1;

	vector<int> temp1,temp2;

	first_search(root->left,temp1);

	first_search(root->right,temp2);

	if(temp1==temp2)

		return 1;

	else

		return 0;

}



int main()

{



}

귀속적인 방법으로 하여 양쪽의 두 좌우 나무가 대칭적인지 판단한다. 즉, 왼쪽 나무의 왼쪽 나무가 오른쪽 나무의 오른쪽 나무인지, 왼쪽 나무의 오른쪽 나무가 오른쪽 나무의 왼쪽 나무인지를 판단한 다음에 적당한 귀속 종지 조건을 선택한다. 즉, 두 좌우 나무의 서쪽에 결점이 없거나 양쪽에 각각 하나의 노드(귀속), 네 개의 결점(이어 귀속)이 있다.또는 다른 상황(귀환), 그리고 주의해야 할 것은 마지막으로 돌아올 때 이 두 값이 같은지 아닌지를 판단하는 것이다
다음은 AC 코드입니다.
 

#include<iostream>

//#include<stack>

#include<queue>

#include <vector>

using namespace std;





 // Definition for binary tree

struct TreeNode {

      int val;

      TreeNode *left;

      TreeNode *right;

      TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};



bool ifduicheng(TreeNode* left_root,TreeNode* right_root)

{



	if(left_root->left==NULL&&left_root->right==NULL&&right_root->left==NULL&&right_root->right==NULL)

	{

		if(left_root->val==right_root->val)

			return true;

		else

			return false;

	}

	else if(left_root->left!=NULL&&left_root->right!=NULL&&right_root->left!=NULL&&right_root->right!=NULL)

	{

		if(ifduicheng(left_root->left,right_root->right)&&ifduicheng(left_root->right,right_root->left))

		{

			if(left_root->val==right_root->val)

				return true;

			else

				return false;

		}

		else

			return false;

	}

	else if(left_root->left!=NULL&&left_root->right==NULL&&right_root->left==NULL&&right_root->right!=NULL)

	{

		if(ifduicheng(left_root->left,right_root->right))

		{

			if(left_root->val==right_root->val)

				return true;

			else

				return false;

		}

		else

			return false;

	}

	else if(left_root->left==NULL&&left_root->right!=NULL&&right_root->left!=NULL&&right_root->right==NULL)

	{

		if(ifduicheng(left_root->right,right_root->left))

		{

			if(left_root->val==right_root->val)

				return true;

			else

				return false;

		}

		else

			return false;

	}

	else

		return false;			

}



bool isSymmetric(TreeNode *root)

{

	if(root==NULL)

		return true;

	if(root->left==NULL&&root->right==NULL)

		return true;

	if((root->left==NULL&&root->right!=NULL)||(root->left!=NULL&&root->right==NULL))

		return false;

	if(root->left!=NULL&&root->right!=NULL)

		return ifduicheng(root->left,root->right);



}

int main()

{

	TreeNode* root;

	root=(TreeNode*)malloc(sizeof(TreeNode));

	root->val=1;

	root->left=(TreeNode*)malloc(sizeof(TreeNode));

	root->left->val=2;

	root->right=(TreeNode*)malloc(sizeof(TreeNode));

	root->right->val=2;

	root->left->left=NULL;

	root->left->right=NULL;

	root->right->left=NULL;

	root->right->right=NULL;



	cout<<isSymmetric(root)<<endl;



}