[BinaryTreeGeneral][Easy] 100. Same Tree

https://leetcode.com/problems/same-tree/description

 

Q. 주어진 두 tree가 동일한 tree인지 판단하라. 

 

 

 

Solution. 

 이런 경우엔 직관적으로 생각해 본다. 

 두 tree가 같기 위해선 leaf의 모양과 해당 data가 같아야 한다. 

 모양이 같다는 의미는 존재하는 위치가 같아야 한다는 것이며, empty leaf를 처리할 수 있으면 결국 판단 가능하다는 것이다. 

 

 BFS로 tree leaf를 순회하여 결과를 비교한다.

 

 코드 

 

List<int> BFS(TreeNode node)
{
    List<int> ret = new List<int>();
    if(node == null)    return ret;

    Queue<TreeNode> buff = new Queue<TreeNode>();
    buff.Enqueue(node);
    while(buff.Count>0)
    {
        TreeNode cur = buff.Dequeue();
        if(cur == null) 
        {
            ret.Add(int.MinValue);
            continue;
        }

        ret.Add(cur.val);
        buff.Enqueue(cur.left);
        buff.Enqueue(cur.right);
    }
    return ret;
}
public bool IsSameTree(TreeNode p, TreeNode q) 
{
    List<int>  p_values = BFS(p);
    List<int>  q_values = BFS(q);
    if(p_values.Count != q_values.Count)
        return false;
    for(int k = 0; k < p_values.Count; ++k)
    {
        if(p_values[k] != q_values[k])
            return false;
    }
    return true;
}

 

결과.