Same Tree

LeetCode에서 난이도 순 정렬했을때, 바로 전 문제로 Binary Tree Inorder Traversal이 있어서 마찬가지로 중위순위 탐색 결과를 저장해서 같은지만 확인하면 되는줄 알았다.

하지만 다음 예에서는 통하지 않는다.

p=[5,4,1,null,1,2,null,null,4,2,null]

q=[5,1,4,4,null,null,2,1,null,null,2]

중위탐색을 하면 null인 경우 -1을 넣었다고 치면

[-1,4,2,1,-1,5,-1,1,2,4,-1] 의 결과가 나온다.

중위탐색 코드:

Binary Tree Inorder Traversal — 有希 (tistory.com)

그래서 중위탐색 알고리즘 코드를 살짝 수정해서 다음과 같은 순서로 값을 밀어넣도록 하였다.

왼쪽->오른쪽으로 탐색,

가장 아래쪽 노드부터 밀어넣는다. Top노드는 가장 마지막에 삽입된다.

사이즈가 다르다면 바로 false,

틀린 값이 있다면 바로 false

모두 통과했다면 true를 반환해주면 된다.

class Solution {
public:
    vector<int> p_val;
    vector<int> q_val;
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr) return false;
        recurrence(p, p_val);
        recurrence(q, q_val);

        if (p_val.size() != q_val.size())
            return false;
        else
            for (int i = 0; i < p_val.size(); ++i)
                if (p_val[i] != q_val[i])
                    return false;

        return true;
    }
    void recurrence(TreeNode* node, vector<int>& tree)
    {
        if (node->left == nullptr && node->right == nullptr)
        {
            tree.push_back(node->val);
            return;
        }
        else if (node->left != nullptr && node->right == nullptr)
        {
            
            recurrence(node->left, tree);
            tree.push_back(-1);
            tree.push_back(node->val);
            return;
        }
        else if (node->left == nullptr && node->right != nullptr)
        {
            tree.push_back(-1);
            recurrence(node->right, tree);
            tree.push_back(node->val);
            return;
        }
        else if (node->left != nullptr && node->right != nullptr)
        {
            recurrence(node->left, tree);
            recurrence(node->right, tree);
            tree.push_back(node->val);
            return;
        }
    }
};