按之字形顺序打印二叉树

Posted on | | reads times

按之字形顺序打印二叉树

题目描述

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

  • 用两个栈，一个存从左到右的节点，一个存从右到左的节点
  • 奇数层从左到右打印，偶数层从右到左打印
  • 每一层单列进list，list再单列进lists
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
function Print(pRoot)
{
    // write code here
    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;
}