[Binary Tree General][Easy] 226. Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/description

 

Q. Tree를 좌우 반전 하라. 

 

Solution. 

 Tree의 leaf의 모든 정보를 depth 별로 저장하고, 그 반대로 parnet와 link 하면 될 것 같다. 

 

 Code 

 

public TreeNode InvertTree(TreeNode root) 
{
    if(root == null)    return root;
    Queue<TreeNode> qBuff = new Queue<TreeNode>();
    qBuff.Enqueue(root);
    List<List<TreeNode>> cache = new List<List<TreeNode>>();
    int depth = 1;
    while(qBuff.Count > 0)
    {
        int cnt = qBuff.Count;
        List<TreeNode> nodes = new List<TreeNode>();
        bool hasLeaf = false;
        for(int q = 0; q < depth; ++q)
        {
            TreeNode cur = q<cnt ? qBuff.Dequeue() : null;
            nodes.Add(cur);
            qBuff.Enqueue(cur==null ? null : cur.left);
            qBuff.Enqueue(cur==null ? null : cur.right);

            hasLeaf = hasLeaf==false ? cur!=null : hasLeaf;
        }
        if(!hasLeaf)    break;

        if(cache.Count > 0)
        {
            for(int q = depth-1; q >= 0; --q)
            {
                TreeNode cur = q<nodes.Count ? nodes[q] : null;
                int idxParent = q/2;
                if(cache[cache.Count-1][idxParent] == null)
                    continue;
                    
                if(q%2 == 0)  cache[cache.Count-1][idxParent].right = cur;
                else          cache[cache.Count-1][idxParent].left = cur;
            }
        }
        cache.Add(nodes);
        depth *= 2;
    }

    return root;
}

 

결과 

 

Acceptable 하지만, 뭔가 코드가 생각보다 복잡해 졌다. 

 

이전엔 어떤 식으로 풀었었나 다시 확인해 본다. 

 

이전 방식은 그냥 child의 위치를 swap하는 간단한 방식이다. 

음. 

전체 tree의 반전도 단일 노드의 반전으로 같은 결과를 얻을 수 있다는 것을 다시 리마인드 해 본다. 

 

코드 

TreeNode ITree(TreeNode node)
{
    if(node == null)    return node;

    var right = node.right;
    node.right = ITree(node.left);
    node.left = ITree(right);

    return node;
}

public TreeNode InvertTree(TreeNode root) 
{
    return ITree(root);
}

 

 

코드양의 차이처럼 속도의 차이도 좀 난다.