題目：

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).

For example:

Given binary tree?[3,9,20,null,null,15,7],

3

/ \

9 20

/ \

15 7

return its zigzag level order traversal as:

[

[3],

[20,9],

[15,7]

]

題意及分析：給出一個橫向遍歷的二叉樹，要求給出 按照Z字形橫向遍歷的每一層 的點。這道題我們可以用stack來求解，簡單來講就是把每一層添加到一個stack里面，然后遍歷輸出結(jié)果的同時將遍歷點的子節(jié)點添加到一個新的stack里面(先添加左子節(jié)點還是右子節(jié)點根據(jù)上一層添加的順序)，遍歷完之后將新的stack賦值給stack進行下一層的遍歷。代碼如下：

代碼：

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class Solution {

public List> zigzagLevelOrder(TreeNode root) {

List> res=new ArrayList<>();

TreeNode node=root;

Stack stack =new Stack<>();

if(node!=null)

stack.push(node);

int leftOrRight=0;//0為先遍歷左子樹，1為右子樹

while(!stack.isEmpty()){

Stack nextStack =new Stack<>();

List list=new ArrayList<>();

while(!stack.isEmpty()){

TreeNode temp=stack.pop();

list.add(temp.val);

if(leftOrRight==0){

if(temp.left!=null)

nextStack.push(temp.left);

if(temp.right!=null)

nextStack.push(temp.right);

}else{

if(temp.right!=null)

nextStack.push(temp.right);

if(temp.left!=null)

nextStack.push(temp.left);

}

}

if(leftOrRight==0)

leftOrRight=1;

else {

leftOrRight=0;

}

res.add(new ArrayList<>(list));

//System.out.println(list);

list.clear();

stack=(Stack) nextStack.clone ();;

nextStack.clear();

}

return res;

}

}

總結(jié)

以上是生活随笔為你收集整理的leetcode103JAVA_[LeetCode] 103. Binary Tree Zigzag Level Order Traversal Java的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。