[Binary Tree][Easy] 101. Symmetric Tree

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

 

 

Q. root node를 기준으로 값이 mirror 되는 tree인지 여부를 반환하라. 

 

 

Solution. 

  직관적으로 해 본다. 

  같은 level의 tree node를 순서대로 모두 구한 후에 

  그 반을 기준으로 양 노드들을 비교 해 주면 될 것 같다. 

  동레벨의 노드를 얻기위해서는 queue를 사용하면 된다. 

 

 아이디어대로 코드를 만들어 본다. 

 

 bool isSymmetric(TreeNode* root) 
{
    queue<TreeNode*> qBuff;
    qBuff.push(root);

    while (!qBuff.empty())
    {
        int size = qBuff.size();
        vector<TreeNode*> vNodes;
        for (int q = 0; q < size; ++q)
        {
            TreeNode* node = qBuff.front(); 
            qBuff.pop();
            vNodes.push_back(node);
            if (node != NULL)
            {
                qBuff.push(node->left);
                qBuff.push(node->right);
            }
        }

        // 얻은 노드들을 중앙을 기준으로 비교 해 준다.
        for (int q = 0; q < vNodes.size() / 2; ++q)
        {
            TreeNode* nodeA = vNodes[q];
            TreeNode* nodeB = vNodes[vNodes.size()-q-1];

            if (nodeA == NULL || nodeB==NULL)
            {
                if(nodeA != nodeB)
                    return false;
            }
            else if (nodeA->val != nodeB->val)
                return false;
        }
    }
    return true;
}

 

최적해는 아닌듯 보이지만, 해결은 되었다. 

더 빠른 다른 답들은 재귀함수를 쓴 로직들로 접근이 조금 다르다. 

걔들은 후에 체크 해 보기로 하자.