题目链接:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
1. 题目介绍(Binary Tree Zigzag Level Order Traversal)
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
【Translate】: 给定二叉树的根,返回其节点值的锯齿级顺序遍历。(例如,从左到右,然后下一个层将从右到左,并在两者之间交替)。
【测试用例】:
示例1:
示例2:
【条件约束】:
2. 题解
2.1 双堆栈
原题解来自于 tjcd 的 JAVA Double Stack Solution.
根据题意,要求Zigzag遍历,而不是像上一个 Binary Tree Level Order Traversal 依次按照顺序将遍历到的点数据存入列表中。而是要满足:①、奇数层的节点数据按照从左到右的顺序存入列表;②、偶数层的节点数据按照从右到左的顺序存入列表。这里就是通过双堆栈进行交替输出,一个堆栈存储奇数层,一个堆栈存储偶数层,关键就在于放入堆栈的顺序,奇序就从左到右放,偶序就从右向左放,最后输出即可。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if(root == null) return ans;Stack<TreeNode> s1 = new Stack<>();Stack<TreeNode> s2 = new Stack<>();s1.push(root);TreeNode curr = new TreeNode();while(!s1.isEmpty() || !s2.isEmpty()){List<Integer> list = new ArrayList<>();while(!s1.isEmpty()){curr = s1.pop();list.add(curr.val);if(curr.left != null) s2.push(curr.left);if(curr.right != null) s2.push(curr.right);}ans.add(list);list = new ArrayList<>();while(!s2.isEmpty()){curr = s2.pop();list.add(curr.val);if(curr.right != null) s1.push(curr.right);if(curr.left != null) s1.push(curr.left);}if(!list.isEmpty()) ans.add(list);}return ans;}
}