面试题32_3：之字形打印二叉树

之字形打印二叉树。并非广度优先搜索，需要使用两个辅助栈。

C++版本

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#include <algorithm>
#include "TreeNode.h"
using namespace std;

// 之字形打印二叉树
void Printf(TreeNode* root){
    if(root == nullptr)
        return ;
    // 定义两个辅助栈
    stack<TreeNode*> levels[2];
    // 当前行
    int current = 0;
    int next = 1;

    levels[current].push(root);
    while(!levels[0].empty() || !levels[1].empty()){
        TreeNode* pNode = levels[current].top();
        levels[current].pop();
        cout<<pNode->val<<", ";
        if(current == 0){
            if(pNode->left != nullptr)
                levels[next].push(pNode->left);
            if(pNode->right != nullptr)
                levels[next].push(pNode->right);
        }
        else{
            if(pNode->right != nullptr)
                levels[next].push(pNode->right);
            if(pNode->left != nullptr)
                levels[next].push(pNode->left);
        }
        if(levels[current].empty()){
            cout<<endl;
            current = 1 - current;
            next = 1 - next;
        }
    }
}


int main()
{
    TreeNode* pNode8 = CreateBinaryTreeNode(8);
    TreeNode* pNode6 = CreateBinaryTreeNode(6);
    TreeNode* pNode10 = CreateBinaryTreeNode(10);
    TreeNode* pNode5 = CreateBinaryTreeNode(5);
    TreeNode* pNode7 = CreateBinaryTreeNode(7);
    TreeNode* pNode9 = CreateBinaryTreeNode(9);
    TreeNode* pNode11 = CreateBinaryTreeNode(11);

    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode9, pNode11);

    printf("====Test1 Begins: ====
");
    printf("Actual Result is: 
");
    Printf(pNode8);
    printf("
");
    return 0;
}