剑指offer32:从上到下打印二叉树

题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印

思路：典型的队列使用

void PrintFromTopToBottom(TreeNode* root) {
        if(root==nullptr)
            return ;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            cout<<node->val<<" ";
            if(node->left!=nullptr)
                q.push(node->left);
            if(node->right!=nullptr)
                q.push(node->right);
        }
    }

拓展1： 分层从上到下打印二叉树打印

分层打印时需要统计每一层的节点个数，当此层节点打印完时，输出换行符. 设置两个标记分别记录当前层剩余节点数和下一层的节点总数，当当前层打印完时，更新当前层与下一层节点数目.

void PrintFromTopToBottom(TreeNode* root) {
        if(root==nullptr)
            return ;
        queue<TreeNode*> q;
        q.push(root);
        int level =1;
        int next_l=0;
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            level--;
            cout<<node->val<<" ";
            if(node->left!=nullptr){
                q.push(node->left);
                next_l++;
            }
            if(node->right!=nullptr){
                q.push(node->right);
                next_l++;
            }
            if(level==0){
                cout<<endl;
                level=next_l;
                next_l=0;
            }
        }
    }

拓展2：之字形打印二叉树

如上图所示，对于奇数层从左往右打印，偶数层从右往左打印. 在打印当前层节点时，子节点在下一层打印时是反向的,使用栈存储节点，使其先进后出. 使用两个栈，当是打印奇数层时，将子节点从左往右压栈，下一层打印时就能先打印右子节点. 当打印偶数层时，将子节点从右往左入栈，下一层节点打印时就能先打左子节点.

void PrintFromTopToBottom(TreeNode* root) {
    if(root==nullptr)
        return;
    stack<TreeNode*> st1;
    stack<TreeNode*> st2;
    st1.push(root);
    int level=1;
    while(!st1.empty() || !st2.empty()){
        if(level % 2!=0){//奇数层
            while(!st1.empty()){
                TreeNode* node = st1.top();
                st1.pop();
                cout<<node->val;
                if(node->left!=nullptr)
                    st2.push(node->left);
                if(node->right!=nullptr)
                    st2.push(node->right);
            }
            cout<<endl;
        }else{//偶数层
            while(!st2.empty()){
                TreeNode* node=st2.top();
                st2.pop();
                cout<<node->val;
                if(node->right!=nullptr)
                    st1.push(node->right);
                if(node->left!=nullptr)
                    st1.push(node->left);
            }
            cout<<endl;
        }
        level++;
    }
}