검지 offer 지그재그 인쇄 두 갈래 나무

1. 문제 설명

제목: 함수는 지그재그 순서에 따라 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로 인쇄하고, 두 번째 줄은 오른쪽에서 왼쪽으로 인쇄하고, 세 번째 줄은 왼쪽에서 오른쪽으로 인쇄합니다. 다른 줄은 이와 같습니다.

2. 분석

앞에는 지점을 인쇄 두 갈래 나무로 나누어 여기가 지그재그로 되어 있다는 것을 설명한다.예:

//                8
//        4              12
//     2     6       10      14
//   1  3  5  7     9 11   13  15

인쇄 결과는 다음과 같습니다.

8
12 4
2 6 10 14
15 13 11 9 7 5 3 1

0층을 인쇄한 결과 8, 하나의 요소로 아무런 문제가 없었다..

1층을 인쇄한 결과 124가 나왔습니다. 여기에 문제가 생겼습니다. 1층을 저장할 때 412가 되어야 합니다. 순서가 반대인 것 같습니다. 창고를 사용해야 하는 것 아닙니까..

2층을 인쇄한 결과 261014, 앞의 층 방문 순서는 124, 우리가 2층을 저장할 때 141062가 되어야 한다.여기에 문제가 하나 있습니다. 우리가 노드 12를 방문할 때 오른쪽 노드를 먼저 방문하고 그 다음에 왼쪽 노드를 방문해야 합니다.액세스 노드 4도 마찬가지입니다.

3층을 방문할 때와 1층을 방문하는 방법과 순서는 같다..

따라서 우리는 노드의 짝짓기를 주의해야 한다. 두 개의 창고를 사용하여 현재 층의 노드와 다음 층의 노드를 각각 저장해야 한다.

3. 소스 코드:

vector<vector<int> > Print(TreeNode* pRoot)
{
    vector<vector<int> > results;
    if(pRoot == NULL)
        return results;
    // 1pop() 
    stack<TreeNode*> stack1;
    // 2pop() 
    stack<TreeNode*> stack2;

    stack1.push(pRoot);
    // ， 
    while(!stack1.empty() || !stack2.empty())
    {
        // 1 pop() vector ， , push 2 
        if(!stack1.empty())
        {
            vector<int> res;
            while(!stack1.empty())
            {
                TreeNode* pNode = stack1.top();
                stack1.pop();

                res.push_back(pNode->val);

                if(pNode->left != NULL)
                    stack2.push(pNode->left);
                if(pNode->right != NULL)
                    stack2.push(pNode->right);
            }
            results.push_back(res);
        }
        // 2 pop() vector ， , push 1 
        else if(!stack2.empty())
        {
            vector<int> res;
            while(!stack2.empty())
            {
                TreeNode* pNode = stack2.top();
                stack2.pop();

                res.push_back(pNode->val);

                if(pNode->right != NULL)
                    stack1.push(pNode->right);
                if(pNode->left != NULL)
                    stack1.push(pNode->left);
            }
            results.push_back(res);
        }
    }
    return results;
}

4. 결론

지그재그가 두루 돌아다니는 것은 매우 복잡하다. 우리는 예를 들어 구체적으로 분석해야만 방법과 규칙을 찾을 수 있다.예를 들어 두 개의 창고를 찾으려면 두 개의 창고를 찾으면 서로 교환해야 한다