首页 > 代码库 > [LeetCode] 103. Binary Tree Zigzag Level Order Traversal Java
[LeetCode] 103. Binary Tree Zigzag Level Order Traversal Java
题目：
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里面，然后遍历输出结果的同时将遍历点的子节点添加到一个新的stack里面(先添加左子节点还是右子节点根据上一层添加的顺序)，遍历完之后将新的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<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
TreeNode node=root;
Stack<TreeNode> stack =new Stack<>();
if(node!=null)
stack.push(node);
int leftOrRight=0; //0为先遍历左子树，1为右子树
while(!stack.isEmpty()){
Stack<TreeNode> nextStack =new Stack<>();
List<Integer> 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<TreeNode>) nextStack.clone ();;
nextStack.clear();
}
return res;
}
}
[LeetCode] 103. Binary Tree Zigzag Level Order Traversal Java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。