Leet Code - 101. Symmetric Tree(C++)

예제: Symmetric Tree

문제
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

NOTE:
Bonus points if you could solve it both recursively and iteratively.

풀이

이진트리 두 개가 주어졌을 때, 이들이 좌우 대칭인지 true, false를 반환하는 문제이다.
지난번에 풀었던 Same Tree와 상당히 유사한 문제이다.(어찌나 비슷한지 멘트도 복붙중이다😅)

필자는 재귀함수로 풀었는데, 다 풀고 나니 문제 끝에 재귀를 사용하면 추가 점수를 준다고 되어있더라! 그래서 보너스 점수는 어디에..?

각설하고, 지난번 Same Tree와 매우 유사하게 대칭이 되도록 자식노드의 path를 타고 가며 같지 않으면 바로 false를 return해주는 형태이다.

전체적인 소스코드는 아래와 같다.

소스 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	bool isSymmetric(TreeNode* root) {
		if (root == NULL) return true;
		return solve(root->left, root->right);
	}

	bool solve(TreeNode* left, TreeNode* right) {
		if (left == NULL && right == NULL) return true;
		if ((left == NULL && right != NULL) || (left != NULL && right == NULL)) return false;
		if (left->val != right->val) return false;

		return solve(left->left, right->right) && solve(left->right, right->left);
	}
};

풀이 후기

Same Tree 문제를 풀어 보아서 그런지 쉽게 풀 수 있었다.
가끔 이런 문제를 버스를 타고 가는 시간동안 폰코딩으로 푸는데, 느낌이 상당히 새롭다. 아, 물론 폰코딩은 비추다.😊