100. Same Tree

문제

위와 같이 두개의 트리가 주어지면 두개의 트리가 같은지 다른지 return 하는 함수를 작성하는 것이다.

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) {
        //작성
    }
}

일단 확실한건

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

여기서 만약 val이 서로 같으면 이제 각각의 자식 노드들을 비교해 줘야 한다.

class Solution {
    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;
    }
}

따라서 위와 같이 작성 해준다.

하지만 예시에서도 나왔듯이 트리 자체가 null 일 수가 있다. 이를 처리해 줘야 한다.

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

둘 중 하나라도 null 이면 둘을 서로 비교한 값을 return 해준다.