77.按之字形顺序打印二叉树.md

77.按之字形顺序打印二叉树

题目描述

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

示例1

输入

{8,6,10,5,7,9,11}

返回值

[[8],[10,6],[5,7,9,11]]

思路 & 解答

1. 借助双向链表，初始化一个添加方向boolean值，先将根节点添加进去：

2. 获取list里面剩下的元素的个数，挨个取出就是一层，取出的时候，如果reverse为true，则往链表的第0个索引位置添加，否则直接在后面添加，然后判断每一个取出来的节点的左右节点是不是为空，不为空则加入链表。

3. 每一层处理完之后，将list加入结果集中，然后翻转reverse的值，继续判断list是不是为空，执行第二步循环。

代码如下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution{
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        LinkedList<TreeNode> nodes = new LinkedList<>();
        ArrayList <ArrayList<Integer>>results = new ArrayList();
        boolean reverse = true;
        if(pRoot!=null){
            nodes.add(pRoot);
            while(!nodes.isEmpty()) {
                ArrayList<Integer> integers = new ArrayList();
                int size = nodes.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = nodes.poll();
                    if(reverse){
                        integers.add(node.val);
                    }else{
                        integers.add(0,node.val);
                    }
                    if (node.left!=null){
                        nodes.offer(node.left);
                    }
                    if(node.right!=null){
                        nodes.offer(node.right);
                    }
                }
                if(integers.size()!=0){
                    results.add(integers);
                }
                reverse=!reverse;
            }
        }
        return results;
    }
}

C++ 代码如下：

class Solution {
public:
    vector<vector<int> > Print(TreeNode *pRoot) {
        deque<TreeNode *> nodes;
        vector<vector<int>> results;
        bool reverse = true;
        if (pRoot != NULL) {
            nodes.push_back(pRoot);
            while (nodes.size() > 0) {
                vector<int> integers;
                int size = nodes.size();
                for (int i = 0; i < size; i++) {
                    TreeNode *node = nodes.front();
                    nodes.pop_front();
                    if (reverse) {
                        integers.push_back(node->val);
                    } else {
                        integers.insert(integers.begin(), node->val);
                    }
                    if (node->left != NULL) {
                        nodes.push_back(node->left);
                    }
                    if (node->right != NULL) {
                        nodes.push_back(node->right);
                    }
                }
                if (integers.size() != 0) {
                    results.push_back(integers);
                }
                reverse = !reverse;
            }
        }
        return results;
    }
};

空间复杂度由于借助了额外的list，为O(n)，时间复杂度上，由于每个节点进入队列又出来，为O(2n)，也是O(n)。