二叉树的之字形层序遍历

我不是女神ヾ 2022-12-04 02:27 97阅读 0赞

# 二叉树的之字形层序遍历 #

## 1、参考资料 ##

https://www.nowcoder.com/practice/47e1687126fa461e8a3aff8632aa5559

## 2、题目要求 ##

> **题目描述**

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）  
例如：给定的二叉树是 `{3,9,20,#,#,15,7}`

![image-20200905002707893][]

该二叉树之字形层序遍历的结果是

[
    [3],
    [20,9],
    [15,7]
    ]

> **示例**

输入

{1,#,2}

输出

[[1],[2]]

## 3、代码思路 ##

基于双栈的层序遍历

1.  我们可以使用 `queue` 对二叉树进行层序遍历，现在要求进行之字形层序遍历，即第一层正序输出，第二层逆序输出，第三层又正序输出，以此类推。。。
2.  但凡牵涉到逆序，我们就会想到栈这个数据结构，因为栈先进后出，先进入栈的数据最后出栈，所以栈能实现逆序的效果
3.  起初写代码的时候我卡壳了，因为我只用了一个栈，抠破脑袋也捋清思路，现在想想，这不挺简单的一个道理嘛~~~
4.  假设我们现在遍历到二叉树第二层，首先，为了实现逆序遍历，二叉树第二层的节点肯定都保存在一个栈中(`stack1`)，这是毋庸置疑的，那么下一层节点咋办呢？肯定不能往 `stack1` 里面塞，因为塞了之后就把 `stack1` 的栈顶给封住了，第二层剩余的节点就取不出来了，所以我们还需要一个栈(`stack2`)存储下一层的节点
5.  在经历上述操作后，`stack1` 变为了空栈，`stack2` 存储了第三层的节点，然后我们接着遍历 `stack2`，将第四层的节点存入 `stack1` 中
6.  仔细想了想，我这里的设计思路还有点牛逼(自恋一下)，引用 `JVM` 幸存者区的一句话：谁空谁是 `to`，这点在我代码中也有体现，`stackOut` 表示存储当前层节点的栈，`stackIn` 表示存储下一层节点的栈，`stack1` 和 `stack2` 的身份在 `stackOut` 和 `stackIn` 之间不停地切换
7.  关于遍历的方向：从左往右遍历(正向遍历)时，我们需要先将当前节点的左节点 `stackIn` 中；从右往左遍历(反向遍历)时，我们需要先将当前节点的右节点 `stackIn` 中

--------------------

举例说明

1.  以下面这颗二叉树举例说明，先将根节点 `1`压入 `stack1` 中
    
        1 
             / \
            2    3
           /      \
          4        5
2.  首先遍历的方向为正向遍历(`isForward = true`，从左往右遍历)时
    
    1.  此时 `stack1` 为 `stackOut`，`stack2` 为 `stackIn`，遍历完成后 `stack1` 为空，`stack2` 中存储着第二层的节点
    2.  遍历时不断 `pop()` 出 `stackOut` 中的节点，添加至 `ArrayList` 中，得到第一层的顺序遍历
    
        1         <-------当前层
             / \
            2    3
           /      \
          4        5
3.  遍历完第一层后转换方向，变为从右往左遍历(`isForward = false`)，
    
    1.  此时 `stack2` 为 `stackOut`，`stack1` 为 `stackIn`，遍历完成后 `stack2` 为空，`stack1` 中存储着第三层的节点
    2.  遍历时不断 `pop()` 出 `stackOut` 中的节点，添加至 `ArrayList` 中，得到第二层的逆序遍历
    
        1
             / \
            2    3      <-------当前层
           /      \
          4        5
4.  以此类推

## 4、代码实现 ##

代码

class Solution {
        
        public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        
    
            ArrayList<ArrayList<Integer>> zigzagOrder = new ArrayList<>();
    
            // Guard safe
            if (root == null) {
        
                return zigzagOrder;
            }
    
            // 双栈
            Deque<TreeNode> stack1 = new LinkedList<>();
            Deque<TreeNode> stack2 = new LinkedList<>();
            stack1.push(root); // 将根节点压入栈中
            boolean isForword = true; // 初始顺序为从左往右遍历
    
            // 但凡只要有一个栈中还有元素，则证明当前层还有节点
            while (stack1.isEmpty() == false || stack2.isEmpty() == false) {
        
                // 谁空谁来存储下一层节的点，谁不空谁存储了当前层节点
                Deque<TreeNode> stackOut = stack1.isEmpty() ? stack2 : stack1;
                Deque<TreeNode> stackIn = stack1.isEmpty() ? stack1 : stack2;
                zigzagOrder.add(new ArrayList<>());
                // 遍历完当前层的节点
                while (stackOut.isEmpty() == false) {
        
                    // 栈顶节点出栈
                    TreeNode curNode = stackOut.pop();
                    // 添加至 ArrayList
                    zigzagOrder.get(zigzagOrder.size() - 1).add(curNode.val);
                    if (isForword) {
        
                        // 如果方向是从左往右，则先遍历当前节点的左节点
                        pushNode(stackIn, curNode.left);
                        pushNode(stackIn, curNode.right);
                    } else {
        
                        // 如果方向是从右往左，则先遍历当前节点的右节点
                        pushNode(stackIn, curNode.right);
                        pushNode(stackIn, curNode.left);
                    }
                }
                isForword = !isForword; // 改变方向
            }
    
            return zigzagOrder;
        }
    
        private void pushNode(Deque<TreeNode> stack, TreeNode node) {
        
            if (node != null) {
        
                stack.push(node);
            }
        }
    }
    
    class TreeNode {
        
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
        
            this.val = val;
        }
    }

[image-20200905002707893]: /images/20221123/ed619341ca9644759f0bb115aab8d674.png