23.03.13. 풀었던 문제들

Leetcode 101. Symmetric Tree

 문제를 받자마자 1번의 순회로 해결할 수 있는 경우가 있을 것 같아 left를 순회하는 것과 right를 순회하는 것을 따로따로 복잡하게 생각해 보다가 vector에 left inorder 탐색 결과와 right inorder 탐색 결과를 넣고 이 둘을 비교하는 방식을 썼다. 그러나 이렇게 풀면 틀린다. 다르게 생긴 tree지만 같게 들어가는 경우가 생긴다.

 

 틀린 걸 확인하고 다르게 코드를 짜기 시작했다.

 

 각 탐색에서 left와 right를 한번에 탐색하고, left와 right가 같고, 탐색가능할 때(null이 아닐 때) 그 때 좌우 탐색 결과를 보는 거다.

• 만약 left와 right 둘 다 null이면 symmetric이다.
• 만약 left와 right 둘 중 하나만 null이면 symmetric이 아니다.
• 만약 left와 right의 value가 다르면 symmetric이 아니다.
• 위 경우가 모두 해당되지 않는다면
  • left의 left child, right의 right child를 recurse한다
  • left의 right child, right의 left child를 recurse한다.
  • 이렇게 하는 이유는 symmetric을 보아야 하기 때문이다. left->left는 right->right와 / left->right는 right->left와 symmetric이다.

 

 사실 번뜩이는 직관으로 어떻게 풀긴 했는데 어떤 증명으로 이게 답이 되는지는 잘 모르겠다.

 일단 binary tree가 symmetric이려면 root의 left subtree, right subtree를 비교해야 한다. 이 때 각각의 subtree의 같은 level을 비교해야 한다.

• level 0은 root
• level 1은 root->left, root->right를 비교하면 된다.
• level 2는 root->left->left와 root->right->right / root->left->right와 root->right->left를 비교하면 된다.
• deeper하게 갈수록 left->left와 right->right / left->right와 right->left를 비교하면 된다는 것을 알 수 있다.
• 따라서 탐색할 때, left와 right를 두고 left subtree의 left subtree, right subtree의 right subtree / left subtree의 right subtree, right subtree의 left subree를 비교하게 recurse하면 된다.

// Runtime 0 ms Beats 100%
// Memory 16.4 MB Beats 84.12%
class Solution {
public:
    bool inorder(TreeNode *left, TreeNode *right){
        if(left == NULL && right == NULL) return true;
        // if(left == NULL && right != NULL) return false;
        // if(left != NULL && right == NULL) return false;
        // 이 두 줄을 아래 줄로 표현할 수 있다.
        if(left == NULL || right == NULL) return false;
        if(left->val != right->val) return false;

        return inorder(left->left, right->right) && inorder(left->right, right->left);    
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return inorder(root->left, root->right);
    }
};

 

시간복잡도

 worst case 모든 vertex에 대해 inorder method를 수행하게 되므로 O(n)이다.

 

공간복잡도

 추가 공간을 사용하지 않으므로 O(1). inorder 함수는 tree의 height만큼 recurse한다. 따라서 O(h). binary tree라면 O(logn)이지만 입력이 binary tree가 아닐 수도 있기 때문에 O(h)이다. 이 때 worst cast h == n이므로 O(n).