【LeetCode】103.Binary Tree Zigzag Level Order Traversal解題報告
20447 ワード
転載は出典を明記してください。http://blog.csdn.net/crazy1235/article/details/51524241
Subject
出典:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
Given a binary tree，return the zigzag level order trversal of its nodes’values.(e，from left to right，then right to left for the next level and altername between)
For example：Given binary tree｛3,9,20，菗，菗，15,7｝
このテーマは前の2つの問題ととても似ています。
【LeetCode】102.Binary Tree Level Order Traversal解題報告は、トップから下に降りて、左から右へと順番が回っています。
【LeetCode】107.Binary Tree Level Order Traversal II解題報告書は下から上へ、左から右へと順番が回っています。
このタイトルはトップから下に行くという意味で、「ジグザグ」という順番で結点を出力します。（1階は左から右、2階は右から左、3階は左から右へ…順に類推）。
Solution
ソロ1
第1の案は【102】主題の非再帰的方法を用いて修正される。
主に現在の結点がある階層、または現在の層の結点の個数を記録します。
逆方向の層が必要な場合は、Collection.reverse（）方法を呼び出すか、またはLinked ListのaddFirst（）方法を使用するか、ArayListのadd（0，E）方法を使用することもできる（この方法は効率が高くないので、コピー配列が必要）。
再帰的方式によって。
テーマの再帰的方法を改造する。
階層という変数があるので、再帰する度に、level%2が0かどうかを判断する必要があります。
LeetCodeプラットフォームRun Timeは1 msです。
beat 96.02%のof java submissions.
ソロ3
このテーマのTagsは「Stock」のラベルを示しています。説明はスタック方式でできます。
ソロ4
ジグザグ階層出力は、主に上の層が左から右に、下の層が右から左に出力されます。だから標識が必要です。
このタイトルの「Discuss」からDeque-双端列を使用した解法が見られます。
flagsがtrueの場合は、左から右にノードを付けて列の最後に追加します。このようにチームの最後からpollLast（）の順番は右から左になります。flagsがfalseである場合、ノードを右から左に対頭に追加します。このように対頭pollFirst()の場合、順番は左から右になります。
【102】【107】【103】これらのテーマはほぼ同じです。すべての階層は、出力二叉樹を巡回します。順番が違うだけです。
みんなは一対三を挙げることができます。どうやって下の方から上の方へ行くかを考えられます。
ビンゴ~
Subject
出典:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
Given a binary tree，return the zigzag level order trversal of its nodes’values.(e，from left to right，then right to left for the next level and altername between)
For example：Given binary tree｛3,9,20，菗，菗，15,7｝
3
/ \
9 20
/ \
15 7[
[3],
[20,9],
[15,7]
]
このテーマは前の2つの問題ととても似ています。
【LeetCode】102.Binary Tree Level Order Traversal解題報告は、トップから下に降りて、左から右へと順番が回っています。
【LeetCode】107.Binary Tree Level Order Traversal II解題報告書は下から上へ、左から右へと順番が回っています。
このタイトルはトップから下に行くという意味で、「ジグザグ」という順番で結点を出力します。（1階は左から右、2階は右から左、3階は左から右へ…順に類推）。
Solution
ソロ1
第1の案は【102】主題の非再帰的方法を用いて修正される。
主に現在の結点がある階層、または現在の層の結点の個数を記録します。
逆方向の層が必要な場合は、Collection.reverse（）方法を呼び出すか、またはLinked ListのaddFirst（）方法を使用するか、ArayListのadd（0，E）方法を使用することもできる（この方法は効率が高くないので、コピー配列が必要）。
/**
* 3ms
*
* beats 14.87% of java submissions
*
* @author jacksen
* @param root
* @return
*/
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int i = queue.size(); //
boolean flag = false;
TreeNode tempNode = null;
List<Integer> singleLevel = new ArrayList<>();
while (!queue.isEmpty()) {
if (i == 0) {//
//
if (flag) {
Collections.reverse(singleLevel);
}
result.add(singleLevel);
//
flag = !flag;
i = queue.size();
singleLevel = new ArrayList<>();
}
tempNode = queue.poll();
singleLevel.add(tempNode.val);
--i;
if (tempNode.left != null) {
queue.add(tempNode.left);
}
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
if (flag) {
Collections.reverse(singleLevel);
}
result.add(singleLevel);
return result;
} /**
* 2ms
*
* beats 60.36% of java submissions
*
* @author jacksen
* @param root
* @return
*/
public List<List<Integer>> zigzagLevelOrder5(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int i = queue.size(); //
boolean flag = true;
TreeNode tempNode = null;
LinkedList<Integer> singleLevel = new LinkedList<>();
while (!queue.isEmpty()) {
if (i == 0) {//
//
result.add(singleLevel);
//
i = queue.size();
singleLevel = new LinkedList<>();
flag = !flag;
}
tempNode = queue.poll();
if (flag) {
singleLevel.add(tempNode.val);
} else {
singleLevel.addFirst(tempNode.val);
}
--i;
if (tempNode.left != null) {
queue.offer(tempNode.left);
}
if (tempNode.right != null) {
queue.offer(tempNode.right);
}
}
result.add(singleLevel);
return result;
}再帰的方式によって。
テーマの再帰的方法を改造する。
階層という変数があるので、再帰する度に、level%2が0かどうかを判断する必要があります。
/**
*
* ,
*
* 1ms
* eats96.02% of java submissions
*
* @author jacksen
* @param root
* @return
*/
public List> zigzagLevelOrder2(TreeNode root) {
List> result = new ArrayList>();
// levelRecursion(root, result, 0, false);
levelRecursion2(root, result, 0);
return result;
}
/**
*
*/
private void levelRecursion(TreeNode node, List> result,
int level, boolean flag) {
if (node == null) {
return;
}
if (result.size() < level + 1) {//
result.add(new LinkedList());
}
if (flag) {
((LinkedList) result.get(level)).addFirst(node.val);
} else {
result.get(level).add(node.val);
}
levelRecursion(node.left, result, level + 1, !flag);
levelRecursion(node.right, result, level + 1, !flag);
}
/**
* level addFirst，
*
* @param node
* @param result
* @param level
*/
private void levelRecursion2(TreeNode node, List> result,
int level) {
if (node == null) {
return;
}
if (result.size() < level + 1) {//
result.add(new LinkedList());
}
if (level % 2 != 0) {
((LinkedList) result.get(level)).addFirst(node.val);
} else {
result.get(level).add(node.val);
}
levelRecursion2(node.left, result, level + 1);
levelRecursion2(node.right, result, level + 1);
}
LeetCodeプラットフォームRun Timeは1 msです。
beat 96.02%のof java submissions.
ソロ3
このテーマのTagsは「Stock」のラベルを示しています。説明はスタック方式でできます。
/**
*
* 3ms
* beats 14.87% of java submissions
*
* @author jacksen
* @param node
* @return
*/
public List> zigzagLevelOrder3(TreeNode root) {
List> result = new ArrayList>();
if (root == null) {
return result;
}
Stack forwardStack = new Stack<>();
Stack retrorseStack = new Stack<>();
forwardStack.push(root);
TreeNode tempNode = null;
List singleList = new ArrayList<>();
while (!forwardStack.isEmpty() || !retrorseStack.isEmpty()) {
while (!forwardStack.isEmpty()) {
tempNode = forwardStack.pop();
singleList.add(tempNode.val);
if (tempNode.left != null) {
retrorseStack.push(tempNode.left);
}
if (tempNode.right != null) {
retrorseStack.push(tempNode.right);
}
}
if (!singleList.isEmpty()) {
result.add(singleList);
singleList = new ArrayList<>();
}
while (!retrorseStack.isEmpty()) {
tempNode = retrorseStack.pop();
singleList.add(tempNode.val);
if (tempNode.right != null) {
forwardStack.push(tempNode.right);
}
if (tempNode.left != null) {
forwardStack.push(tempNode.left);
}
}
if (!singleList.isEmpty()) {
result.add(singleList);
singleList = new ArrayList<>();
}
}
return result;
}
ソロ4
ジグザグ階層出力は、主に上の層が左から右に、下の層が右から左に出力されます。だから標識が必要です。
このタイトルの「Discuss」からDeque-双端列を使用した解法が見られます。
/**
* deque
* 3ms
* beats 14.87% of java submissions
*
* @author https://leetcode.com/discuss/89116/java-bfs-with-deque
*
* @param root
* @return
*/
public List> zigzagLevelOrder4(TreeNode root) {
List> result = new ArrayList>();
if (root == null) {
return result;
}
boolean flag = true;
TreeNode tempNode = null;
TreeNode lastNode = root;
List singleLevel = new ArrayList<>();
Deque deque = new LinkedList<>();
deque.offer(root);
while (!deque.isEmpty()) {
tempNode = flag ? deque.pollFirst() : deque.pollLast();
singleLevel.add(tempNode.val);
if (flag) {// left->right
if (tempNode.left != null) {
deque.offerLast(tempNode.left);
}
if (tempNode.right != null) {
deque.offerLast(tempNode.right);
}
} else {
if (tempNode.right != null) {
deque.offerFirst(tempNode.right);
}
if (tempNode.left != null) {
deque.offerFirst(tempNode.left);
}
}
if (tempNode == lastNode) {
result.add(singleLevel);//
singleLevel = new ArrayList<>();
lastNode = flag ? deque.peekFirst() : deque.peekLast();
flag = !flag;
}
}
return result;
}
flagsがtrueの場合は、左から右にノードを付けて列の最後に追加します。このようにチームの最後からpollLast（）の順番は右から左になります。flagsがfalseである場合、ノードを右から左に対頭に追加します。このように対頭pollFirst()の場合、順番は左から右になります。
【102】【107】【103】これらのテーマはほぼ同じです。すべての階層は、出力二叉樹を巡回します。順番が違うだけです。
みんなは一対三を挙げることができます。どうやって下の方から上の方へ行くかを考えられます。
ビンゴ~