[leetcode] Binary Tree Zigzag Level Order Traversal

发布时间：2020-12-14 04:18:32 所属栏目：大数据来源：网络整理

导读：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,15,7] , 3 / 9 20 / 15 7 ret

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,15,7],

    3
   /   9  20
    /     15   7

return its zigzag level order traversal as:

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

分析：题目要求之字形层次遍历一个二叉树。

思路一：层次遍历肯定想到用BFS，习惯于用队列queue实现，这个问题实现思路也比较简单，维持一个boolean类型变量表示：0代表从右到左，1代表从左到右就可以了。

就不贴上代码了。

思路二：既然可以用队列，肯定也可以用栈做。维持两个栈实现功能，代码如下：

 1 class Solution {
 2     List<List<Integer>> res = new ArrayList<>();
 3     Stack<TreeNode> l_r = new Stack<>();
 4     Stack<TreeNode> r_l = new Stack<>();
 5     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
 6         if ( root == null ) return res;
 7         l_r.push(root);
 8         List<Integer> a = new ArrayList<>();
 9         a.add(root.val);
10         res.add(a);
11         while ( !l_r.isEmpty() || !r_l.isEmpty() ){
12             if ( !l_r.isEmpty() ){
13                 int size = l_r.size();
14                 List<Integer> list = new ArrayList<>();
15                 for ( int i = 0 ; i < size ;i ++ ){
16                     TreeNode t = l_r.pop();
17                     if ( t.right != null ) {
18                         list.add(t.right.val);
19                         r_l.push(t.right);
20                     }
21                     if ( t.left != null ) {
22                         list.add(t.left.val);
23                         r_l.push(t.left);
24                     }
25                 }
26                 if ( !list.isEmpty() ) res.add(list);
27             }
28             if ( !r_l.isEmpty()){
29                 int size = r_l.size();
30                 List<Integer> list = new ArrayList<>();
31                 for ( int i = 0 ; i < size ;i ++ ){
32                     TreeNode t = r_l.pop();
33                     if ( t.left != null ) {
34                         list.add(t.left.val);
35                         l_r.push(t.left);
36                     }
37                     if ( t.right != null ) {
38                         list.add(t.right.val);
39                         l_r.push(t.right);
40                     }
41 
42                 }
43                 if ( !list.isEmpty() ) res.add(list);
44             }
45         }
46         return res;
47     }
48 }

??? AC 2ms，看了一下1ms的答案，都是用queue做的，因为比较熟了。就不写queue的代码了。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!