[Leetcode] 98. Validate Binary Search Tree

Identifying the Problem

subtree가 tree내에 있다면, true 없다면, false를 리턴한다.

Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true

Organizing thoughts

먼저 크게 4가지로 subtree와 tree의 경우를 표로 나타낼 수 있다.

Tree	Subtree	Result
null	null	true
o	null	false
null	o	false
o	o	true / false

IDEA

[1] tree를 탐새하면서, tree->val과 subtree->val 이 같은 순간이 오면,

    두 트리를 동시에 탐색하면서 완전히 동일한지 판단한다.

    하지만, 위 예시에서 불필요하게 tree의 level 0과 subtree의 level 0이 동일한지 확인해야한다.

[2] 따라서 1의 단점을 보완해, subtree의 깊이가 같은 곳만 (가장 밑에서의 높이가 같은 곳의 node) 를 뽑아 subtree와        동일한지 판단한다.

[3] tree와 subtree의 값들을 배열에 저장해 subtree 배열의 값이 tree 내에 존재하는지 파악한다.

    하지만, 이는 문제의 의도와는 맞지 않으므로 이 방법으로 풀지는 않겠다.

Sourcecode

소스코드는 2번의 아이디어로 작성되었다.

 

정답 코드의 flow (편의상 subtree의 root를 s, tree의 root를 t로 놓겠다)

 

1. t와 s 둘 다 null이면 true, 둘 중 하나만 null이면 false 리턴

2. s의 깊이를 파악

3. t에서 밑에서 s깊이의 높이에 위치한 노드를 모두 저장

4. 저장된 노드와 s가 같은지 반복하며 비교

 

정답 코드의 출처

19ms C++ solution beats 99.9% - LeetCode Discuss

class Solution {
    vector<TreeNode*> nodes;

public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (!s && !t) return true; //둘다 null이면 true
        if (!s || !t) return false; //하나만 null이면 false

        getDepth(s, getDepth(t, -1)); //s의 깊이를 구하고, s의 깊이에 해당하는 node저장

        for (TreeNode* n: nodes) //저장한 node들과 s가 같은지 확인
            if (identical(n, t))
                return true;

        return false; //defalut 값 false
    }

    int getDepth(TreeNode* r, int d) 
    {
        if (!r) return -1;
        // -1인 이유 : 1. 가장 아래서부터 높이를 더하기 때문
        //2. t에서 s와 높이가 같은 노드를 저장해야 하는 데, 
        //   s의 높이를 구하는 과정에서 d가 0보다 클 경우, 
        //   저장 node에 s의 node가 들어가는 것을 막고자
        
        int depth = max(getDepth(r->left, d), getDepth(r->right, d)) + 1;
        //중위순회하며 높이 구하기
        
        if (depth == d) //t-node 의 높이가 s의 높이와 같다면 해당 t-node 저장
            nodes.push_back(r);

        return depth;
    }

    bool identical(TreeNode* a, TreeNode* b) 
    {
        if (!a && !b) return true; //둘다 null이면 true
        if (!a || !b || a->val != b->val) return false; 
        //하나만 null이면 혹은 둘의 값이 다르면 false 

        return identical(a->left, b->left) && identical(a->right, b->right);
        //false 가 하나라도 잡히면 false 리턴
    }
};