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

按之字形顺序打印二叉树

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

算法思想一：层次遍历+栈

解题思路：

主要利用层次遍历二叉树的节点，并根据奇偶层添加二叉树的节点

算法流程：

1、特殊情况：如果树的根节点为空，则直接返回【】

2、初始化：返回列表 res ，二叉树层索引 index，辅助栈

3、层次遍历循环当栈为空跳出：

1、新建列表tmp，用于临时存储当前层打印结果

2、当前层打印循环：循环次数为当前层节点数量

1、出栈：栈底元素，记为 node

2、打印：将所在层节点值添加到 tmp中

3、添加子节点：若 node 的左右子树不为空，则入栈

3、根据index判断所在层是奇数层还是偶数层：

1、若为奇数层：将tmp直接添加到res中

2、若为偶数层：将tmp倒序添加到res中

4、index 加1

4、返回打印结果 res

图解:

代码展示：

Python版本

class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = []
        # 辅助栈
        stack = [pRoot]
        # 记录层数
        index = 1
        while stack:
            tmp = []
            for i in range(len(stack)): 
                node = stack[0]
                stack = stack[1:]
                tmp.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            # 判断所在树的层数，根据层数对 tmp 是否倒序存储
            if index % 2 == 0:
                res.append(tmp[::-1])
            else:
                res.append(tmp)
            index += 1 
        return res

复杂度分析：

时间复杂度O(N)：N为二叉树的节点数量，层次遍历、进出栈

空间复杂度O(N)：最差情况下，即当树为满二叉树时，最多有 N/2 个树节点同时在 stack 中，使用 O(N) 大小的额外空间。

算法思想二：层次遍历+双端队列（奇偶层逻辑分离）

解题思路：

方法一代码简短、容易实现；但需要判断每个节点的所在层奇偶性，即冗余了 N 次判断。通过将奇偶层逻辑拆分，可以消除冗余的判断。

算法流程：

与方法一对比，仅层次遍历过程有差别，此方法使用的是双端队列存储二叉树的节点

BFS 循环：循环打印奇 / 偶数层，当 deque 为空时跳出；
1、打印奇数层：从左向右打印，先左后右加入下层节点；
2、若 deque 为空，说明向下无偶数层，则跳出；
3、打印偶数层：从右向左打印，先右后左加入下层节点；

代码展示：

JAVA版本

public class Solution {
    public ArrayList Print(TreeNode pRoot) {
        Dequedeque = new LinkedList<>();
        ArrayList res = new ArrayList<>();
        if(pRoot != null) deque.add(pRoot);
        while(!deque.isEmpty()) {
            // 打印奇数层
            ArrayListtmp = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                // 从左向右打印
                TreeNode node = deque.removeFirst();
                tmp.add(node.val);
                // 先左后右加入下层节点
                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
            res.add(tmp);
            if(deque.isEmpty()) break; // 若为空则提前跳出
            // 打印偶数层
            tmp = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                // 从右向左打印
                TreeNode node = deque.removeLast();
                tmp.add(node.val);
                // 先右后左加入下层节点
                if(node.right != null) deque.addFirst(node.right);
                if(node.left != null) deque.addFirst(node.left);
            }
            res.add(tmp);
        }
        return res;
    }

}