题解 | #按之字形顺序打印二叉树#

按之字形顺序打印二叉树

http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

题目的主要信息：

给定一个二叉树，返回该二叉树的之字形层序遍
第一层从左向右，下一层从右向左，一直这样交替

举一反三：

学习完本题的思路你可以解决如下题目：

BM26. 求二叉树的层次遍历

BM35. 判断是否是完全二叉树

方法一：非递归层次遍历（推荐使用）

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

按照层次遍历按层打印二叉树的方式，每层分开打印，然后对于每一层利用flag标记，第一层为false，之后每到一层取反一次，如果该层的flag为true，则记录的数组整个反转即可。

//奇数行反转，偶数行不反转
if(flag) 
    reverse(row.begin(), row.end());

但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue），事实上，队列中的值大有玄机，让我们一起来看看：当根节点进入队列时，队列长度为1，第一层节点数也为1；若是根节点有两个子节点，push进队列后，队列长度为2，第二层节点数也为2；若是根节点一个子节点，push进队列后，队列长度为为1，第二层节点数也为1。由此，我们可知，每层的节点数等于进入该层时队列长度，因为刚进入该层时，这一层每个节点都会push进队列，而上一层的节点都出去了。

int n = temp.size();
for(int i = 0; i < n; i++){
    //访问一层
}

具体做法：

step 1：首先判断二叉树是否为空，空树没有打印结果。
step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面，初始化flag变量。
step 3：每次进入一层，统计队列中元素的个数，更改flag变量的值。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
step 4：每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
step 5：访问完这一层的元素后，根据flag变量决定将这个一维数组直接加入二维数组中还是反转后再加入，然后再访问下一层。

图示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        TreeNode head = pRoot;
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        if(head == null)
            //如果是空，则直接返回空list
            return res; 
        //队列存储，进行层次遍历
        Queue<TreeNode> temp = new LinkedList<TreeNode>(); 
        temp.offer(head);
        TreeNode p;
        boolean flag = true;
        while(!temp.isEmpty()){
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList<Integer>();  
            int n = temp.size();
            //奇数行反转，偶数行不反转
            flag = !flag; 
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++){
                p = temp.poll();
                row.add(p.val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(p.left != null)
                    temp.offer(p.left);
                if(p.right != null)
                    temp.offer(p.right);
            }
            //奇数行反转，偶数行不反转
            if(flag)  
                Collections.reverse(row);
            res.add(row);
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        TreeNode* head = pRoot;
        vector<vector<int> > res;
        if(head == NULL)
            //如果是空，则直接返回空vector
            return res;
        //队列存储，进行层次遍历 
        queue<TreeNode*> temp; 
        temp.push(head);
        TreeNode* p;
        bool flag = true;
        while(!temp.empty()){
            //记录二叉树的某一行
            vector<int> row;  
            int n = temp.size();
            //奇数行反转，偶数行不反转
            flag = !flag; 
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++){
                p = temp.front();
                temp.pop();
                row.push_back(p->val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(p->left)
                    temp.push(p->left);
                if(p->right)
                    temp.push(p->right);
            }
            //奇数行反转，偶数行不反转
            if(flag) 
                reverse(row.begin(), row.end());
            res.push_back(row);
        }
        return res;
    }
};

Python实现代码

import queue

class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        head = pRoot
        res = []
        if not head:
            # 如果是空，则直接返回空list
            return res 
        # 队列存储，进行层次遍历
        temp = queue.Queue() 
        temp.put(head)
        flag = True
        while not temp.empty():
            # 记录二叉树的某一行
            row = [] 
            # 奇数行反转，偶数行不反转
            flag = not flag 
            n = temp.qsize()
            # 因先进入的是根节点，故每层节点多少，队列大小就是多少
            for i in range(n): 
                p = temp.get()
                row.append(p.val)
                # 若是左右孩子存在，则存入左右孩子作为下一个层次
                if p.left:
                    temp.put(p.left)
                if p.right:
                    temp.put(p.right)
            # 奇数行反转，偶数行不反转
            if flag: 
                row = row[::-1]
            res.append(row)
        return res

复杂度分析：

时间复杂度： $O (n)$ ，每个节点访问一次，因为reverse的时间复杂度为 $O (n)$ ，按每层元素reverse也相当于 $O (n)$
空间复杂度： $O (n)$ ，队列的空间最长为 $O (n)$

方法二：双栈法（扩展思路）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

方法一用到了反转函数，反转我们能想到什么？肯定是先进后出的栈！

我们可以利用两个栈遍历这棵二叉树，第一个栈s1从根节点开始记录第一层，然后依次遍历两个栈，遍历第一个栈时遇到的子节点依次加入第二个栈s2中，即是第二层：

//遍历奇数层
while(!s1.empty()){ 
    TreeNode* node = s1.top();
    //记录奇数层
    temp.push_back(node->val); 
    //奇数层的子节点加入偶数层
    if(node->left)  
        s2.push(node->left);
    if(node->right) 
        s2.push(node->right);
    s1.pop();
}

而遍历第二个栈s2的时候因为是先进后出，因此就是逆序的，再将第二个栈s2的子节点依次加入第一个栈s1中：

while(!s2.empty()){ 
    reeNode* node = s2.top();
    //记录偶数层
    temp.push_back(node->val);  
    //偶数层的子节点加入奇数层
    if(node->right)  
        s1.push(node->right);
    if(node->left) 
        s1.push(node->left);
    s2.pop();
}

于是原本的逆序在第一个栈s1中又变回了正序，如果反复交替直到两个栈都空为止。