按之字形顺序打印二叉树

发表于

描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

题解

  • 首先判断二叉树是否为空，空树没有遍历结果
  • 建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面
  • 每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数
  • 每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问
  • 访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层
  • 二维数组中奇数下标(偶数层)数组反转
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
41
42
43
44
45
46
47
48
49
50
51
package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

/**
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
*/
func Print( pRoot *TreeNode ) [][]int {
    // write code here
    if pRoot == nil {
        return nil
    }

    queues := []*TreeNode{pRoot}
    levels := [][]int{}

    for len(queues) > 0 {
        n := len(queues)
        level := []int{}
        for i := 0; i < n; i++ {
            root := queues[0]
            queues = queues[1:]
            level = append(level, root.Val)
            if root.Left != nil {
                queues = append(queues, root.Left)
            }
            if root.Right != nil {
                queues = append(queues, root.Right)
            }
        }

        k1 := len(level)
        k2 := len(levels)
        // 当前层为偶数层,从右到左遍历.(逆转数组level)
        if k2 % 2 == 1 {
            for index := 0; index < k1/2; index++ {
                level[index], level[k1-index-1] = level[k1-index-1], level[index]
            }
        }

        levels = append(levels, level)
    }

    return levels
}