[LeetCode C++] 100. Same Tree

⭐️ 난이도

Easy

 

---

⭐️ 문제

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

Same Tree - LeetCode

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

binary tree 두개 p와 q의 root가 주어졌을 때, 두 개의 트리가 서로 같은지 아닌지 여부를 확인하는 함수를 만드시오.

 

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

두 개의 binary tree의 구조가 서로 같고, 노드의 값이 같으면 같은 트리라고 판단한다.

 

 

---

⭐️ Follow-up

X

 

---

⭐️ Idea flow

 

DFS를 통해 해결할 수 있는 문제였다.

 

두 root 노드에서부터 시작하여 

1) 현재 노드의 값이 같은지 확인

2) 두 노드의 left child가 있는지 확인. 만일 둘 다 있다면 DFS 진행

3) 두 노드의 right child가 있는지 확인. 만일 둘 다 있다면 DFS 진행

 

위의 조건에 맞지 않는다면 두 개의 트리가 같지 않다는 이야기이고 false를 반환하면 된다.

 

 

---

⭐️ Code

/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q){
        if(!p && !q){
            return true;
        }
        // 둘 중 하나만 nullptr이거나, 둘의 값이 다를 때
        if((!p && q) || (p && !q) || (p->val != q->val)){
            return false;
        }
        
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        
    }
};

 

 

---

⭐️ Feedback

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

기존에 DFS를 사용해서 문제를 풀었을 때에는 함수의 return형을 void로 해놓고, local 변수를 선언하여 해당 변수를 return 하는 방식을 사용했다.

이번에는 return형이 bool인 DFS 코드를 짜보았는데, 익숙하지 않았다.

다음 문제에서 DFS를 쓰게 되면 이와 같은 방식을 여러 번 사용해보아야겠다.