剑指offer——按之字形顺序打印二叉树

AI那点小事

发布于 2020-04-20 12:38:28

4180

概述

题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路

首先定义两个堆栈left和right,并定义二维数组ans来存放结果序列，一维数组tmp来存放中间结果。首先将根结点压入left，根结点的元素追加到tmp，之后tmp追加到ans，之后tmp清空。之后当left和right中至少一个非空，进入循环。若left非空，则进入循环至left为空，每出栈一个结点node，依次将node的右孩子和左孩子压入right，并把右孩子和左孩子的元素追加到tmp，重复上述过程直至循环结束，之后若tmp非空，则把tmp追加到ans，之后tmp清空。之后若right非空，进入循环。每出栈一个结点node，依次将node左孩子和右孩子压入right，并把左孩子和右孩子的元素追加到tmp，重复上述过程直至循环结束，之后若tmp非空，则把tmp追加到ans，之后tmp清空。

C++ AC代码

#include <iostream>
#include <stack>
#include <vector> 
using namespace std; 

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

class Solution {
    public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            stack<TreeNode*> left;
            stack<TreeNode*> right;
            vector<vector<int> >ans;
            vector<int> tmp;
            if(!pRoot){
                return ans;
            } 
            tmp.push_back(pRoot->val);
            ans.push_back(tmp);
            tmp.clear();
            left.push(pRoot);
            while(!left.empty() || !right.empty()){
                while(!left.empty()){
                    TreeNode* node = left.top();
                    left.pop();
                    if(node->right){
                        right.push(node->right);
                        tmp.push_back(node->right->val);
                    }
                    if(node->left){
                        right.push(node->left);
                        tmp.push_back(node->left->val);
                    }
                }
                if(!tmp.empty()){
                    ans.push_back(tmp);
                    tmp.clear();
                }
                while(!right.empty()){
                    TreeNode* node = right.top();
                    right.pop();
                    if(node->left){
                        left.push(node->left);
                        tmp.push_back(node->left->val);
                    }
                    if(node->right){
                        left.push(node->right);
                        tmp.push_back(node->right->val);
                    }
                }
                if(!tmp.empty()){
                    ans.push_back(tmp);
                    tmp.clear();
                }
            }
            return ans;
        }       
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

node.js