[LeetCode]100. Same tree (Java)

[LeetCode]100. Same tree (Java)

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

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

같은 트리인지 확인해보는 알고리즘 문제!

트리쪽 알고리즘 개념을 확실하게 잡고 싶어서 당분간은 트리쪽을 파볼까 한다.

먼저 트리의 전개 방식을 보면 Root - Left - Right로 스캔중이기 때문에 이진트리를 Preorder 방식으로 순회중이다.

tree 객체 분석

 // 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;
      }
  }

객체 선언부분만 보더라도 TreeNode(root, left, right) 세가지 경우일뿐이라서 쉽게 해결가능하다 그러나 여기서 노드의 차수가 증가하면 복잡해질것이다.

풀이

0. null 확인
1. root 값 비교
2. 재귀적으로 left right 비교

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.left, q.left) && isSameTree(p.right, q.right);
    }
}

이번 문제에 대한 풀이를 찾아보던 중 DFS (깊이 우선 탐색)에 대해 알게 되었는데 개념이 제대로 이해가 가지 않아 DFS 분석을 따로 해봐야겠다