[자바] Leetcode 100 - Same Tree

어쩌다 면접이 잡혀서 발등에 불떨어진 느낌으로 부랴부랴 문제 푸는중 ㅎ

친구한테 리트코드 추천 받아서 Difficulty Easy단계부터 풀고 있는데, 어렵지는 않다. 하지만 최적화는 정말 끝이 없고, 똑똑한 사람들은 이 세상에 많다는 걸 계속해서 깨닫게 된다. 

---

TreeNode 2개를 파라미터로 던져주면 그 2개의 TreeNode들이 동일한지 아니지를 판별하는 메소드를 짜는 문제다. 

Class TreeNode는 아래처럼 구현되어 있다는 가정하에 메소드 로직만 채우면 된다.

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

내 생각의 흐름은 아래와 같다. 

1. 일단 현재 노드들의 값을 비교해야 하기 때문에 아래와 같은 조건문은 반드시 필요하다. 

- 현재 노드들의 값을 비교해서 같다면 다음 단계를 생각하고, 만약 다르다면 이후를 고민할 필요도 없이 false다. 

 public boolean isSameTree(TreeNode p, TreeNode q) {      
        if(p.val==q.val) 
            return (아직 생각중인 로직)
        
         else return false;
    }

 

2. 현재 노드들의 값이 같다면 현재 노드의 자식들을 비교해야 한다. 각 노드에는 왼쪽 자식과 오른쪽 자식이 있는데, 

그 자식들의 값을 비교하는 로직은 1번이랑 사실상 동일하다. → 그렇다면 재귀를 생각해야겠군! 

근데 자식들 중 하나라도 값이 서로 다르다면 이것도 결국 false다. → 그렇다면 &&로 묶어서 둘 중 하나라도 false만 false를 리턴하도록 해야겠다! 

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

 

3. 재귀로 계속해서 값들을 비교해 나가다가 마지막 노드에 도달해서 자식이 없을 수 있다. 그렇다면 이제 비교대상인 두 개의 노드가 모두 null인 경우와 둘 중 하나만 null인 경우를 나누어서 생각해볼 수 있다. 

- 만약 둘 다 null인 경우, 이건 그냥 끝까지 올 때까지 양쪽 TreeNode가 동일했다는 뜻이니까 true를 리턴한다 

- 둘 중 하나만 null인 경우, 이건 모양새 자체가 두 개의 TreeNode가 다르다는 뜻이니까 false를 리턴한다  

 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);
        
         else return false;
    }

코드의 전부다! 생각보다 간단하게 풀어서 행복하다!