[LeetCode] 100. Same Tree

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

Same Tree - LeetCode

LeetCode - Same Tree

문제 유형 : 트리, 탐색

문제 난이도 : Easy

 

문제

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.

 

두 이진 트리의 루트 p와 q가 주어진다.두 트리가 같은지 판별하시오.

값과 구조가 동일해야 합니다.

 

풀이

트리를 순회하는 로그를 담는 문자열을 만든다.

전위 순회로 하면서, 각 노드의 값을 열거하는 식으로 하였다.

 

노드가 빈 노드면 문자 n을 붙인다. 구조적으로 같은지 확인하기 위해서이다.

두 트리의 순회로 만들어진 각각의 문자열을 비교해주면 된다.

 

코드

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 traverse(TreeNode* root, string &s) {
        if(root == nullptr) {
            s += "n";
            return;
        }

        s += to_string(root -> val);
        traverse(root -> left, s);
        traverse(root -> right, s);
    }

    bool isSameTree(TreeNode* p, TreeNode* q) {
        string s1 = "";
        string s2 = "";

        traverse(p, s1);
        traverse(q, s2);

        return s1 == s2;
    }
};