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

谁借莪１个温暖的怀抱￠ 2022-02-25 17:18 182阅读 0赞

## 题目描述 ##

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

解题思路：

利用一个双端队列，一个方向标志，当本行是从左往右遍历时，将其子节点按 左节点 右节点 的顺序先后加入到队列头；当本行是从右往左遍历时，将其子节点按 右节点 左节点 的顺序先后加入到队列尾；

class Solution {
    public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> res;
            if(!pRoot)
                return res;
            
            deque<TreeNode*> deq;
            deq.push_back(pRoot);
            bool ltor = false;
            
            while(!deq.empty()) {
                int sz = deq.size();
                ltor = !ltor;
                
                vector<int> row;
                while(sz--) {
                    if(ltor) {
                        pRoot = deq.back();
                        deq.pop_back();
                        row.push_back(pRoot->val);
                        if(pRoot->left)
                            deq.push_front(pRoot->left);
                        if(pRoot->right)
                            deq.push_front(pRoot->right);
                    }
                    else {
                        pRoot = deq.front();
                        deq.pop_front();
                        row.push_back(pRoot->val);
                        if(pRoot->right)
                            deq.push_back(pRoot->right);
                        if(pRoot->left)
                            deq.push_back(pRoot->left);
                    }
                }
                
                res.push_back(row);
            }
            return res;
        }
        
    };