리트코드 - 100. Same Tree

리트코드 - 100. Same Tree

출처 - https://leetcode.com/problems/same-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

두 이진 트리 p와 q의 루트가 주어지면 이들이 동일한지 확인하는 함수를 작성하세요.
두 개의 이진 트리가 구조적으로 동일하고 노드의 값이 동일한 경우 동일한 것으로 간주됩니다.

 

의사코드

함수 isSameTree if (p == null && q == null)     return true else if (p == null || q == null)     return false if (p.val == q.val)     return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); return false;

 

풀이코드

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

 

코드설명

재귀적으로 구현하는 방식이다.

이전에 노드의 최대 depth를 구하는 문제(링크)와 방법은 비슷하다.

 

이번에는 상위 노드부터 하위노드를 탐색한다.

먼저 p와 q 모두 null이면 true를 리턴하고, 둘 중에 하나만 null인 경우 false를 리턴한다.

 

이렇게 null값을 처리했으면, p와 q의 값을 확인해서 같은 경우에만 if문을 진행한다.

p와 q가 같지 않으면 false가 되고, p와 q의 val값이 같은 경우에는 left와 right를 각각 다시 함수에 넣어 비교한다.

 

시간복잡도 - O(n)

공간복잡도 - O(n) (주어진 트리의 최대 높이)

 

문제를 풀며 생각한 흐름과 배운 점

재귀를 떠올렸을 때 상위부터 순회해야 할지 하위부터 순회해야 할지 고민하는게 중요한 것 같다.

노드 자체는 재귀를 사용하는 것이 편하지만 로직이 복잡해질 경우에는 고려해야 할 것이 많다.

아직은 easy 수준의 문제라 그렇게 어렵지는 않았다.

 

다른코드

class Solution {
    ArrayList list = new ArrayList<>();
  
    public boolean isSameTree(TreeNode p, TreeNode q) {
       ArrayList list1 = new ArrayList<>();
        returnTreeList(p);
        list1.addAll(list);
        list.clear();
        returnTreeList(q);
        
      //  System.out.println(list1);
      //   System.out.println(list2);
        // if(list1.equals(list)){
        //   return true;
        // }else{
        //   return false;
        // }
        return(list1.equals(list));
    }

    public ArrayList returnTreeList(TreeNode n){
    
      if(n==null){
       //System.out.println(list);
       list.add(null);
       return list;
       
      }
        list.add(n.val);
      
       returnTreeList(n.left);
       returnTreeList(n.right);
     
      return list;
    }
    
}

list를 지역변수로 담아서 isSameTree 함수 내에 있는 list1과 비교하고 있다.

런타임도 0ms로 내 코드와 같고, 메모리는 오히려 조금 적게 차지한다.

 

지역변수로 list를 선언해서 계속 호출하지 않는게 재밌는 부분인 것 같다.

그렇지만 list를 제네릭 타입으로하지 않은 점, 지역변수가 단순히 util로 사용되고 있는 점에서 다소 아쉬운 코드인 것 같다.

 

정리

노드를 재귀적으로 순회하는 간단한 방법