关于java:LeetCode103二叉树的锯齿形层序遍历

51次阅读

共计 1922 个字符，预计需要花费 5 分钟才能阅读完成。

题目形容：给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：利用队列和栈遍历二叉树

队列的特点是先进先出，栈的特点是后进先出，所以利用队列和栈来遍历二叉树实现锯齿形遍历，具体过程如下：

首先，如果 root 为空，间接返回空的 List。

如果 root 不为空，申明一个队列 nodes，将 root 节点退出到队列中，申明一个 result，申明一个 boolean 类型的变量 directionFlag，当 directionFlag 为 true 时，从左往右往栈中放入节点；当 directionFlag 为 false 时，从右往左放入节点，而后遍历 nodes 中的节点，遍历过程如下：

首先，用 count 记录以后队列中节点的数量，即为以后层节点的数量，vals 记录以后节点的值，申明一个栈 temp；

从 nodes 中按程序取出 count 个节点，并且将相应的节点值放入 vals 中，同时如果以后节点的左右子节点不为空，依据 directionFlag 判断是按从左到右的程序还是从右往左的程序放入 temp 中。而后将 vals 退出到后果 result 中。

将栈 temp 中的元素全副取出放入 nodes。

反复遍历 nodes 中的节点，直到 nodes 为空。

最初返回 result 即为锯齿形层序遍历的后果。

阐明： 解决办法相似 LeetCode-102- 二叉树的层序遍历 。

import java.util.*;

public class LeetCode_103 {public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {if (root == null) {return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        // 当 directionFlag 为 true 时，从左往右放入节点；当 directionFlag 为 false 时，从右往左放入节点
        boolean directionFlag = true;
        while (!nodes.isEmpty()) {int count = nodes.size();
            List<Integer> vals = new ArrayList<>();
            Stack<TreeNode> temp = new Stack<>();
            while (count > 0) {TreeNode curNode = nodes.poll();
                vals.add(curNode.val);
                if (!directionFlag) {if (curNode.right != null) {temp.push(curNode.right);
                    }
                    if (curNode.left != null) {temp.push(curNode.left);
                    }
                } else {if (curNode.left != null) {temp.push(curNode.left);
                    }
                    if (curNode.right != null) {temp.push(curNode.right);
                    }
                }
                count--;
            }
            // 将栈中的节点取出放入队列中
            while (!temp.isEmpty()) {nodes.add(temp.pop());
            }
            // 每一层遍历后变更程序
            directionFlag = !directionFlag;
            result.add(vals);
        }
        return result;
    }

    public static void main(String[] args) {TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.right = new TreeNode(5);


        for (List<Integer> integers : zigzagLevelOrder(root)) {for (Integer integer : integers) {System.out.print(integer + " ");
            }
            System.out.println();}
    }
}