之字形打印二叉树

发表于 | 分类于

题目

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路

画图分析，使用两个栈进行操作

代码

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
34
35
36
37
38
39
40
function Print(pRoot) {
   const lists = [];
 
   if (pRoot === null) {
     return lists;
   }
 
   const stack1 = [];
   const stack2 = [];
 
   stack2.push(pRoot);
   let i = 1;
   while (stack1.length !== 0 || stack2.length !== 0) {
     const list = [];
 
     // 为奇数层
     if ((i & 1) === 1) {
       while (stack2.length !== 0) {
         const tmp = stack2[stack2.length - 1];
         stack2.pop();
         list.push(tmp.val);
         if (tmp.left !== null) stack1.push(tmp.left);
         if (tmp.right !== null) stack1.push(tmp.right);
       }
     }
     // 为偶数层
     else {
       while (stack1.length !== 0) {
         const tmp = stack1[stack1.length - 1];
         stack1.pop();
         list.push(tmp.val);
         if (tmp.right !== null) stack2.push(tmp.right);
         if (tmp.left !== null) stack2.push(tmp.left);
       }
     }
     ++i;
     lists.push(list);
   }
   return lists;
 }