(C++) - LeetCode (easy) 100. Same Tree

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

Same Tree - LeetCode

tree 순회 문제였습니다.

📕 풀이방법

📔 풀이과정

1. 같은 tree인지 아닌지는 tree 순회 결과를 비교했을 때 같은지 여부로 판단 가능합니다.

2. root -> left자식들 -> right자식들 순으로 순회하는 preorder함수를 구현해 그 결과를 vector에 담아 반환해줍니다. val 값이 null 인 경우도 있기 때문에 이 경우 -1로 채워줘 구분합니다. 서로 다른 p, q에 대해 순환 결과를 vector a, b에 저장합니다.

3. for loop를 수행해 원소가 모두 같은지 판별합니다.

size가 다르다면 memory 참조 error가 날 수 있으므로 바로 false를 반환해줍니다.

---

📕 Code

📔 C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void preorder(TreeNode* tree, vector<int> &v){
        if(tree == nullptr) {v.push_back(-1); return;}
        v.push_back(tree->val);
        preorder(tree->left, v);
        preorder(tree->right, v);
    }
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        vector <int> a, b;
        preorder(p, a);
        preorder(q, b);
        if(a.size() != b.size()) return false;
        for(int i = 0; i < a.size(); i++){
            if(a[i] != b[i]) return false;
        }
        return true;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.