[LeetCode] 100. Same Tree - Java

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

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.

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

---

풀이

풀이 과정

두 개의 이진 트리가 주어졌을 때 두 트리가 같은지 아닌지를 판별하는 문제이다.

트리의 루트부터 시작해 자식노드들을 재귀호출 하여 탐색하며 두 트리 노드의 값이 같은지 확인한다.
각 노드별로 세 가지 경우로 나누어 생각한다.

• 두 노드가 모두 null인 경우
• 하나의 노드가 null인 경우
• 두 노드가 모두 null이 아닌 경우

먼저 두 노드가 모두 null인 경우에는 값은 같다고 볼 수 있다. 또한 다음 노드가 존재하지 않으므로 탐색을 중단하고 true를 return 한다.

// 두 노드가 모두 null인 경우
// 현재 값이 같고 다음 노드를 탐색할 필요가 없으므로 true를  return
if(p == null && q == null) return true;

 

다음으로 둘 중 하나의 노드가 null인 경우에는 값이 다르기 때문에 false를 return 한다.

// 둘 중 하나의 노드만 null인 경우
// 현재 노드가 다르므로 false를 return
if(p == null || q == null) return false;

 

위의 두 경우를 제외하면 두 노드 모두 값을 가지고 있는 경우인데, 이때는 두 노드의 값을 비교하여 같지 않은 경우 false를 return 한다.

// 값이 같지 않은 경우 false
if(p.val != q.val) return false;

 

값이 같으면 왼쪽 노드와 오른쪽 노드를 각각 재귀호출하여 탐색을 계속한다.

// 값이 같으면 왼쪽 노드와 오른쪽 노드를 비교
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

---

최종 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 두 노드가 모두 null인 경우
        // 현재 값이 같고 다음 노드를 탐색할 필요가 없으므로 true를  return
        if(p == null && q == null) return true;

        // 둘 중 하나의 노드만 null인 경우
        // 현재 노드가 다르므로 false를 return
        if(p == null || q == null) return false;

        // 두 노드가 모두 null이 아닌 경우
        // 값이 같지 않은 경우 false
        if(p.val != q.val) return false;

        // 값이 같으면 왼쪽 노드와 오른쪽 노드를 비교
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

---