## Friday, August 14, 2015

### LeetCode OJ - Symmetric Tree

Problem:

Solution:

The key observation is that we can define the mirror check recursively.
A tree is a mirror of another if

1. There are either both null (so return right away), otherwise
2. The root node value must match
3. The left side of left tree is a mirror of right side of the right tree
4. The right side of left tree is a mirror of left side of the right tree

With that, we can easily code the solution as follow:

To simplify testing, I implemented the deserialization logic for the tree used by LeetCode.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/symmetric-tree/

#include "LEET_SYMMETRIC_TREE.h"
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SYMMETRIC_TREE
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
private:
bool isMirror(TreeNode* left, TreeNode* right)
{
if (left == NULL)
{
if (right == NULL)
{
return true;
}
else
{
return false;
}
}
else if (right == NULL)
{
return false;
}
else
{
if (left->val != right->val)
{
return false;
}

if (!isMirror(left->left, right->right))
{
return false;
}

if (!isMirror(left->right, right->left))
{
return false;
}

return true;
}
}
public:
bool isSymmetric(TreeNode* root)
{
if (root == NULL)
{
return true;
}

return isMirror(root->left, root->right);
}
};

TreeNode* ToTree(vector<int> serialized)
{
if (serialized.size() == 0)
{
return NULL;
}
unsigned int i = 1;
TreeNode* root = new TreeNode(serialized[0]);
queue<TreeNode*> queue;
queue.push(root);
while (i < serialized.size())
{
TreeNode* current = queue.front();
queue.pop();
int leftValue = serialized[i++];
int rightValue = serialized[i++];
if (leftValue != 10086) // 10086 represents #
{
TreeNode* leftNode = new TreeNode(leftValue);
current->left = leftNode;
queue.push(leftNode);
}
if (rightValue != 10086) // 10086 represents #
{
TreeNode* rightNode = new TreeNode(rightValue);
current->right = rightNode;
queue.push(rightNode);
}
}

return root;
}
};

using namespace _LEET_SYMMETRIC_TREE;

int LEET_SYMMETRIC_TREE()
{
Solution solution;
int case1Array[] = { 1, 2, 2, 3, 4, 4, 3, 10086, 10086, 10086, 10086, 10086, 10086, 10086, 10086 };
TreeNode* case1 = ToTree(vector<int>(case1Array, case1Array + _countof(case1Array)));
cout << solution.isSymmetric(case1) << endl;

int case2Array[] = { 1, 2, 2, 10086, 3, 10086, 3, 10086, 10086, 10086, 10086 };
TreeNode* case2 = ToTree(vector<int>(case2Array, case2Array + _countof(case2Array)));
cout << !solution.isSymmetric(case2) << endl;

return 0;
}