leetcode103.二叉树的锯齿形层次遍历

leetcode103.二叉树的锯齿形层次遍历

二月 23, 2020

leetcode103. 二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/  \
9 20
    /  \
  15    7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]

我的思路

用两个栈解决怎么遍历的问题。入栈的顺序跟第几层有关。为了方便理解，stack1只表示当前的栈，stack2是下一层，所以中间会有调换的过程。2ms.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Stack<TreeNode>stack1=new Stack<>();//表示当前层
        Stack<TreeNode>stack2=new Stack<>();//表示下一层
        List<List<Integer>>res=new LinkedList<>();
        if(root==null)return res;
        LinkedList<Integer>list=new LinkedList<>();
        int flag=-1;//-1为先左再右，1为先右再左
        stack1.push(root);
        while(!stack1.isEmpty()){
            TreeNode node=stack1.pop();
            list.add(node.val);
            if(flag==-1){
                if(node.left!=null)stack2.push(node.left);
                if(node.right!=null)stack2.push(node.right);
            }else{
                if(node.right!=null)stack2.push(node.right);
                if(node.left!=null)stack2.push(node.left);
            }
            if(stack1.isEmpty()){
                //当前层遍历完了
                res.add(list);
                //System.out.println("list="+list);
                list=new LinkedList<>();
                //交换两个stack
                Stack<TreeNode>tmp=stack1;
                stack1=stack2;
                stack2=tmp;
                //更改flag
                flag*=-1;
            }
        }
        return res;
    }

leetcode 29/100