leetcode-100. Same Tree · Tree + DFS + Queue

주제
두 그루의 두 갈래 나무가 같은지 아닌지를 비교하여 결과를 되돌려줍니다.
생각
1. 반복 해결 DFS
먼저 루트 노드를 판단하고 비어 있으면true로 돌아가기;
만약 텅 비어 있지 않으면false로 돌아가기;
만약 모두 비어 있지 않다면 두 개의 점 값이 같은지 아닌지를 판단하고, 다르면false로 돌아가고, 같으면 왼쪽 나무, 오른쪽 나무로 돌아간다
원본 코드

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isSameTree(TreeNode* p, TreeNode* q) {
13         if(p == nullptr && q == nullptr)
14             return true;
15         else if(p == nullptr || q == nullptr)
16             return false;
17         else
18         {
19             if(p->val == q->val)
20                 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
21             else
22                 return false;
23         }
24     }
25 };

2. 레이어 반복 해결: 대기열
1. 먼저 루트 노드를 판단하고 비어 있으면true로 돌아간다.
2. 비어 있으면 false로 돌아가기;
3. 모두 비어 있지 않으면 새 대열을 만들고 두 마디로 대열에 들어갑니다.만약 대기열이 비어 있지 않다면, 두 요소를 내보내고, 만약 모두 비어 있다면, 계속continue (판단 헤드 노드처럼true를 되돌리는 것이 아니라), 비어 있으면false를 되돌려줍니다.
4. 모두 비어 있지 않으면 이 값이 같은지 아닌지를 판단하고, 같지 않으면false로 돌아간다.만약 같다면 현재 노드의 왼쪽 아이(2개), 오른쪽 아이(2개)를 각각 대열에 넣고 순환한다.
즉, 이런 방법은 과정 중false를 되돌리기 위해서이며, 마지막에 반복을 끝내고true를 되돌리기 위해서이다.
원본 코드

 1 class Solution {
 2 public:
 3     bool isSameTree(TreeNode* p, TreeNode* q) {
 4         if(p == nullptr && q == nullptr)
 5             return true;
 6         else if(p == nullptr || q == nullptr)
 7             return false;
 8         queue tmp;
 9         tmp.push(p); tmp.push(q);
10         while(!tmp.empty())
11         {
12             TreeNode *pp, *qq;
13             pp = tmp.front(); tmp.pop();
14             qq = tmp.front(); tmp.pop();
15             if(pp == nullptr && qq == nullptr)
16                 continue;
17             else if(pp == nullptr || qq == nullptr)
18                 return false;
19             
20             if(pp->val != qq->val)
21                 return false;
22             else
23             {
24                 tmp.push(pp->left); tmp.push(qq->left);
25                 tmp.push(pp->right); tmp.push(qq->right);
26             }
27         }
28         return true;
29     }
30 };