Leetcode 226 Invert Binary Tree 반전 트리

원제 주소

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

제목 설명

Invert a binary tree. 두 갈래 나무 한 그루를 반전시키다.
from

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia: 일화:
This problem was inspired by this original tweet by Max Howell: 이 문제의 영감은 Max Howell의 원시 추문(tweet)에서 나왔다.
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off. Google 직원의 90퍼센트가 당신이 쓴 소프트웨어(Homebrew)를 사용하고 있지만, 당신은 백판에 두 갈래 나무를 반전시키는 알고리즘을 쓸 수 없기 때문에 우리는 당신을 원하지 않습니다.
이 사건에 대해 홈브레우 작가가 화이트보드에서 두 갈래 나무를 뒤집지 못해 구글 면접에서 거절당했다는 평가를 어떻게 해야 할지 궁금하다.
이곳에서는 지나치게 많은 토론을 하지 않고 이 문제를 한 번 보면 된다.

문제 풀이 사고방식

직관적으로 보면 문제의 요구가 매우 명확한데 바로 좌우 대조이다.그러면 어떻게 이루어질까요?각 층의 결점을 오른쪽부터 왼쪽으로 순서대로 하나의 대기열에 추가한 다음 대기열의 결점을 순서대로 이전 층의 결점에 연결하는 것을 고려할 수 있다. (이전 층이 반전을 완성했다고 가정하면)
상술한 사고방식을 실현하려면 우리는 i-1층이 반전이 끝났다고 가정하고 i층에 대해 반전 조작을 실행하려고 한다. 우리는 맨 오른쪽의 결점부터 순서대로 각 결점node를 대열queue Last에 넣고 각 결점의 오른쪽 아이와 왼쪽 아이를 대열queue Cur에 넣는다.이렇게 처리가 끝난 후queueLast에 저장된 것은 i층 결점이 반전된 후 왼쪽에서 오른쪽으로 순서를 정한 다음queueCur의 결점을queueLast의 결점에 순서대로 연결하면 i층의 반전을 완성할 수 있다.

코드

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return NULL;
        queue*> last, lastTmp, cur, curTmp;
        last.push(root);
        cur.push(root->right);
        cur.push(root->left);

        TreeNode* nodeTop, * nodeBottom;
        while (!last.empty()) {
            while (!last.empty()) { //  
                                    //  
                nodeTop = last.front();
                last.pop();
                nodeBottom = cur.front();
                cur.pop();
                nodeTop->left = nodeBottom; //  
                if (nodeBottom) {   //  ， ， 
                    lastTmp.push(nodeBottom);
                    curTmp.push(nodeBottom->right);
                    curTmp.push(nodeBottom->left);
                }
                nodeBottom = cur.front();
                cur.pop();
                nodeTop->right = nodeBottom; //  
                if (nodeBottom) {   //  ， ， 
                    lastTmp.push(nodeBottom);
                    curTmp.push(nodeBottom->right);
                    curTmp.push(nodeBottom->left);
                }
            }
            while (!lastTmp.empty()) {
                last.push(lastTmp.front());
                lastTmp.pop();
            }
            while (!curTmp.empty()) {
                cur.push(curTmp.front());
                curTmp.pop();
            }
        }
        return root;
    }
};

전체 코드https://github.com/Orange1991/leetcode/blob/master/226/cpp/main.cpp
이외에도vector로 이루어진 버전도 있습니다. 참고할 만한 흥미가 있습니다.https://github.com/Orange1991/leetcode/blob/master/226/cpp/s2.cpp

테스트 데이터

before invert : 4 7 2 1 3 6 9 5 4 NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL 
after invert : 4 2 7 9 6 3 1 NULL NULL NULL NULL NULL NULL 4 5 NULL NULL NULL NULL 
before invert : 1 2 3 4 NULL NULL 5 NULL NULL NULL NULL 
after invert : 1 3 2 5 NULL NULL 4 NULL NULL NULL NULL 

2015/8/28