[Binary Tree][DFS] [Easy] 872. Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/description

Leaf-Similar Trees - LeetCode

 

Q. 두 노드가 주어질때, 해당 노드의 leaf node를 한쪽에서 읽었을때, 두 노드의 결과가 같다면 두 노드의 leaf가 비슷하다는 표현을 쓴다. 이때 주어진 누노드의 leaf 노드가 비슷한지 여부를 반환하라. 

 

Solution. 

  이 문제야 말고, Depth First Search가 필요한 문제. 

  직관적인 접근으로 푼다. 

 

void leafSimilar_helper(TreeNode* node, vector<int>& vectBuff)
{
    if (node == NULL)	return;

    if (node->left != NULL)		leafSimilar_helper(node->left, vectBuff);
    if (node->right != NULL)	leafSimilar_helper(node->right, vectBuff);
    if (node->left == NULL && node->right == NULL)
        vectBuff.push_back(node->val);
}

bool leafSimilar(TreeNode* root1, TreeNode* root2)
{
    vector<int> v1, v2;
    leafSimilar_helper(root1, v1);
    leafSimilar_helper(root2, v2);

    if (v1.size() != v2.size())	return false;
    for (int k = 0; k < v1.size(); ++k)
    {
        if (v1[k] != v2[k])	return false;
    }
    return true;
}