572 : Subtree of Another Tree( leetcode / java )

*해결 과정

 

 t라는 트리가 s라는 트리에 포함되는지 확인하는 문제입니다. 간단하게 생각하면 각 root의 val값이 같을 때, 재귀적으로 비교해주면 됩니다. 하지만 예외 상황이 있네요. 아래의 경우입니다.

예외 상황!

 

도대체 왜 val값을 독립적으로 만들지 않고 중복되게 만든 것이야!!

결국 우리는 "모든 노드를 순회하면서" val값이 같은 경우 해당 경우가 있는지 없는지 확인해야 합니다.

 

조건을 세워 봅시다.

 

초기조건 : 둘다 null이면 true입니다. 같다는 의미는 둘 다 leaf노드가 같다는 의미입니다. 혹시 한쪽만 null이면 false입니다. 당연히 s,t중 한 쪽만 특정 자손을 가지면 다르겠지요. 또한 val값이 서로 다르면 false입니다.

 

재귀 조건 + 반환조건 : s.left, t.left 와 s.right, t.right 2가지에 대해서 모두 true false를 확인합니다.

(함수가 boolean형이기 때문에 return이 재귀와 마찬가지입니다.)

 

이렇게 해서, 혹시 true인 Treenode를 찾았다면 바로 정답을 true반환하고 그렇지 않으면 계속 탐색합니다.

 

class Solution {
    
    boolean answer=false;
    
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s.val==t.val && answer==false){
            answer = DFS(s,t);
            if(answer==true) return answer;
        } 
        
        if(s.left!=null) isSubtree(s.left,t);
        if(s.right!=null) isSubtree(s.right,t);
        
        return answer;
    }
    
    public boolean DFS(TreeNode s, TreeNode p){
        if(s==null && p==null) return true;
        if(s==null || p==null) return false;
        if(s.val!=p.val) return false;
        return DFS(s.left,p.left) && DFS(s.right,p.right);
    }
}