描述

题目描述

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

示例
输入:{8,6,10,5,7,9,11}
返回值:[[8],[10,6],[5,7,9,11]]

知识点:二叉树,队列,栈,BFS
难度:⭐⭐⭐


题解

解题思路

一旦看到这种有关顺序的,第一个就要想到用栈或队列实现,有这个思路才能进一步实现、优化。

比如这道题,要求 “第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印”,显然,如果能直接利用栈或队列的特性,就能实现题目要求的各种顺序了。

方法一:双栈

图解

image-20210713225643506

算法流程:
  • 维护两个栈,一个存放奇数层的节点,一个存放偶数层的节点
  • 整型变量level表示当前遍历第几层,奇数则顺序打印,偶数逆序打印, 从第1层开始
  • 分奇数层和偶数层处理
    • 奇数层按顺序,每次偶数层的栈保存偶数层节点,先存左结点,这样等下次pop时就是右节点先打印
    • 偶数层反序,每次奇数层的栈保存偶数层节点,先存右结点,这样等下次pop时就是左节点先打印
Java 版本代码如下:
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null) {
            return res;
        }
        // 存放奇数层的节点
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.push(pRoot);
        // 存放偶数层的节点
        Stack<TreeNode> stack2 = new Stack<>();
        // 表示当前遍历第几层,奇数则顺序打印,偶数逆序打印, 从第1层开始
        int level = 1; 
        while(!stack1.isEmpty() || !stack2.isEmpty()) {
            // 处理奇数层
            if(level % 2 != 0) {
                ArrayList<Integer> list = new ArrayList<>();
                // 奇数层按顺序
                while(!stack1.isEmpty()) {
                    TreeNode node = stack1.pop();
                    if(node != null) {
                        // 收集打印结果
                        list.add(node.val);
                        // stack2保存偶数层节点,先存左结点,这样等下次pop时就是右节点先打印,满足题目要求
                        stack2.push(node.left);
                        stack2.push(node.right);
                    }
                }
                // 收集当前层的结果
                if(!list.isEmpty()) {
                    res.add(list);
                    level++;
                }                 
            } else {
                // 处理偶数层
                ArrayList<Integer> list = new ArrayList<>();        
                while(!stack2.isEmpty()) {
                    TreeNode node = stack2.pop();
                    if(node != null) {
                        list.add(node.val);
                        // 需要按顺序push,因为stack1是用在奇数层按顺序输出结果的
                        stack1.add(node.right);
                        stack1.add(node.left);
                    }
                }
                if(!list.isEmpty()) {
                    res.add(list);
                    level++;
                }
            }
        }        
        return res;
    }
}
Python 版本代码如下:
class Solution:
    def Print(self, pRoot):
        if pRoot==None:
            return []
        stack1=[pRoot]
        stack2=[]
        res1=[]
        res2=[]
        result=[]
        while stack1 or stack2:
            res1=[]
            res2=[]
            # 处理奇数层
            while stack1:
                node=stack1.pop()
                # 按顺序,先存左节点,再存右节点
                if node.left:
                    stack2.append(node.left)
                if node.right:
                    stack2.append(node.right)
                res1.append(node.val)
            # 收集当前层的结果
            if len(res1)!=0:
                result.append(res1)
            # 处理偶数层
            while stack2:
                node=stack2.pop()
                if node.right:
                    stack1.append(node.right)
                if node.left:
                    stack1.append(node.left)
                res2.append(node.val)
            # 收集当前层的结果
            if len(res2)!=0:
                result.append(res2)
        return result
复杂度分析:

时间复杂度 O(N):遍历树的每个结点N
空间复杂度 O(N):题目要求返回的二维列表,不算是额外空间,但栈和List都是需要借助的额外空间

方法二:队列&双向遍历

算法流程:
  • 维护一个双向队列,用于保存当前层的元素
  • 每一层,队列都线加入null,表示每一层的分割点,同事用布尔值遍历表示当前方向是否是从左向右遍历的
  • 进行双向遍历,直到队列中只有分隔符null
  • 遇到层分隔符,表示当前已经在新的一层,接着通过迭代器和反向迭代器,进行每一层遍历结果的收集
Java 版本代码如下:
import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null) {
            return res;
        }
        ArrayList<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        // null表示每一层的分割点
        queue.offer(null);
        queue.offer(pRoot);
        // 当前方向是否是从左向右遍历的,第一层是从左往右的
        boolean toRight = true;
        // 双向遍历,直到队列中只有分隔符null
        while (queue.size() != 1) {
            TreeNode node = queue.poll();
            // 遇到层分隔符,表示当前已经在新的一层
            if (node == null) {
                Iterator<TreeNode> iter = null;
                // 从左往右遍历,从queue的头部元素开始迭代
                if (toRight) {
                    iter = queue.iterator();
                } else {
                    // 从右往左遍历,获取queue的尾部元素的迭代器
                    iter = queue.descendingIterator();
                }
                // 下次遍历的方向要反过来
                toRight = !toRight;
                // 遍历当前层结点,并收集当前层的结果
                while (iter.hasNext()) {
                    TreeNode temp = (TreeNode)iter.next();
                    list.add(temp.val);
                }
                // 保存每一层的结果
                res.add(new ArrayList<Integer>(list));
                list.clear();
                //添加层分隔符
                queue.offer(null);
                // 注意:例如每次遍历到这里,此时Queue队头元素还是当前层的第一个结点,上面只是poll掉分隔符null
                continue;
            }
            // 队列加入下一层的每个结点
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return res;
    }
}
复杂度分析:

时间复杂度 O(N):遍历每个结点
空间复杂度 O(N):有借助到队列实现双向遍历