[Easy] 100. Same Tree

Leetcode 100번 문제는 이진 트리 문제이다. 2개의 이진 트리의 root가 주어진다. 두 개의 이진 트리가 똑같은지 알아내는 문제이다. 여기서 똑같다는 정의는 트리의 형태가 같고 모든 노드의 값들도 같아야 한다. 

#풀이

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
       if (q == null && p == null){
           return true;
       }
        if(q != null && p == null || q == null && p != null){
            return false;
        }
        if(p.val != q.val){ 
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

이 문제는 recursion (재귀)과 DFS (Depth First Search) 깊이 우선 탐색으로  쉽게 풀 수 있다. 위 코드는 재귀적으로 이진 트리 왼쪽 노드들을 순회하고 오른쪽 노드들을 순회한다. 순회하는 과정에서 한쪽의 노드가 먼저 null에 다다르거나, 노드의 값이 다르면 false를 return하고, 아무런 문제 없이 동시에 null에 다다르면 true를  return한다. 아래 코드는 위의 코드를  3줄로 간략하게 줄인것이다. 

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
       if (p == null || q == null) return (p == q);
        if(p.val != q.val) return false;
        return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);
    }
}