Binary Tree Zigzag Level Order Traversal

[LeetCode]

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Total Accepted: 44275 Total Submissions: 165753 Difficulty: Medium

Question

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

Examples

For example:
Given binary tree {3,9,20,#,#,15,7},
     3

    / \

   9  20

      /  \

    15   7
return its bottom-up level order traversal as:
[

  [3],

  [20,9],

  [15,7]

]

Ways

方法一

使用队列的方法。

学习了java队列的使用。在一个队列中，放入第一个元素，取出后，放入左右孩子，再根据左右孩子逐个放入其后相应的孩子。队列为空的时候，说明已经遍历完成。

这个方法非常好，学习了。

加入标志符，根据标识符来判断本层是否倒转

倒序算法：

    Collections.reverse(result);

方法二

使用栈的方法。

使用两个栈，一个栈放本层的节点，另外一个栈放下一层的栈。节点值加入List之后，将两个栈互换。这个方法中要根据本层是否要倒序，判断是否颠倒加入栈中。

栈的主要方法：

    currLevel.push(root);

    TreeNode node = currLevel.pop();

Solution

托管在我的GitHub上：

https://github.com/fuxuemingzhu/ZigzagLevelOrder

Captures

测试结果截图:

Reference

http://www.jiuzhang.com/solutions/binary-tree-zigzag-level-order-traversal/

Date

2015/10/14 23:34:11

巴特西

【LeetCode】 Binary Tree Zigzag Level Order Traversal 解题报告