(Leet Code c++)Same Tree

100. Same Tree

 

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

 

Example 1:

Input: p = [1,2,3], q = [1,2,3] Output: true

Example 2:

Input: p = [1,2], q = [1,null,2] Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2] Output: false

 

Constraints:

• The number of nodes in both trees is in the range [0, 100].
• -104 <= Node.val <= 104

주어진 두 개의 이진 트리가 같은 원소를 가지는지 판단해야 한다.

전위 순회(preorder) = 현재 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문하여 값을 각각 a, b 벡터에 저장했다.

 

만약 a와 b 벡터가 모두 비어있는 경우 true를 리턴,

그렇지 않다면 두 벡터를 비교해 값이 같은지 while문으로 판단하면 된다.

단, 전위 순회를 하면서 값이 없는 경우(NULL) INT_MAX를 넣어 값이 들어가지 않는 경우를 대체했다.

/**
 * 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 * node, vector<int> &v){
        v.push_back(node->val);
        
        if(node->left != NULL){
            preorder(node->left, v);
        }
        else{
            v.push_back(INT_MAX);
        }
        
        if(node->right != NULL){
            preorder(node->right, v);
        }
        else{
            v.push_back(INT_MAX);
        }
    }
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        vector<int> a;
        vector<int> b;
        int aIndex = 0, bIndex = 0;
        bool answer = false;
        
        if(p != NULL){
            preorder(p, a);
        }
        
        if(q != NULL){
            preorder(q, b);
        }
        
        if(a.empty() && b.empty()){
            return true;
        }
        
        while(aIndex < a.size() && bIndex < b.size()){
            if(a[aIndex++] != b[bIndex++]){
                return false;
            }
            answer = true;
        }
        
        return answer;
    }
};