【LeetCode】Binary Tree Zigzag Level Order Traversal解題レポート

1442 ワード

LeetCode

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},

return its bottom-up level order traversal as:

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

Ways
方法1
キューを使用する方法.
Javaキューの使用を学びました.1つの列に最初の要素を入れ、取り出した後、左右の子供を入れ、左右の子供によってそれぞれの子供を入れます.キューが空の場合、説明はすでにループ完了しています.
この方法はとても良くて、勉強しました.
識別子に基づいてレイヤーが反転しているかどうかを判断するフラグを追加
逆順序アルゴリズム:

    Collections.reverse(result);

方法2
スタックを使用する方法.
2つのスタックを使用して、1つのスタックはこのレイヤのノードを配置し、もう1つのスタックは1レイヤのスタックを配置します.ノード値がListに追加されると、2つのスタックが交換されます.この方法では,本層が逆順にするか否かに基づいて,逆さまにスタックに加わるか否かを判断する.
スタックの主な方法:

    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

Linux学習ノート(二):個人Gitサーバの構築

【LeetCode】Implement Queue using Stacks解題レポート