[BinaryTree][Easy] 572. Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree/description/

 

주어진 두개의 tree가 있을 때, 하나의 트리중 일부가 다른 트리와 동일한지 판단하라.

 

모든 노드에 대해 subRoot tree와 같은지 비교하면 될 것이다. 

 

이러면 두번 돌게 되는데... 

 

단일 pass에 모두 처리하는 방법에 대해 고민 필요.

 

코드. 

void isSameTreeHelper(TreeNode* nodeA, TreeNode* nodeB, bool& same)
{
    if (!same)   return;
    if (nodeA == nullptr && nodeB == nullptr)
        return;

    if ((nodeA == nullptr && nodeB != nullptr) || (nodeA != nullptr && nodeB == nullptr))
    {
        same = false;
        return;
    }

    if (nodeA->val != nodeB->val)
    {
        same = false;
        return;
    }

    isSameTreeHelper(nodeA->left, nodeB->left, same);
    isSameTreeHelper(nodeA->right, nodeB->right, same);
}
bool isSubtreeHelper(TreeNode* node, TreeNode* subRoot)
{
    if (node == nullptr)
        return false;

    bool same = true;
    isSameTreeHelper(node, subRoot, same);
    if(same)	return true;

    if (isSubtreeHelper(node->left, subRoot))
        return true;

    if (isSubtreeHelper(node->right, subRoot))
        return true;

    return false;
}

bool isSubtree(TreeNode* root, TreeNode* subRoot) 
{
    return isSubtreeHelper(root, subRoot);
}

 

 

결과.