给一颗二叉树，如何从最下层到根节点依次倒着层序遍历呢？今天我来尝试解决下这个问题。

首先想到当然是二叉树如何层序遍历，最先想到的是队列，那就先来通过队列实现普通的层序遍历吧。

队列依次存储每一个节点的指针，每次遍历将队首元素的左右子树依次入队列，这样就保证了层序遍历的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void LevelTraversal(const BinaryTree *root)
{
  if (root == NULL) return;
  //用来保存每一层的节点指针
  queue<const BinaryTree *> q;
  //首先将根节点入队列
  q.push(root);
  //若队列不为空，继续循环添加节点，否则退出
  while (!q.empty())
  {
    //判断队列中队首节点的左右子树是否为空，若不为空依次进队列
    if (q.front()->left != NULL) q.push(q.front()->left);
    if (q.front()->right != NULL) q.push(q.front()->right);
    //该节点的左右子树已经入队列，因此可以输出并出队列了
    cout << q.front()->data << " ";
    q.pop();
  }
}

那如果要实现从下到上，并且每一层的节点为一行输出呢？

一开始想到了栈，先进后出嘛，不就可以倒过来了。

但是还要保证每一层元素的顺序，只用栈不知道该怎么实现。

因此想到了用一个临时队列来保存下一层的元素，之后把这个临时队列遍历的队列并清空。

代码实现如下：

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
void InvertedLevelTraversal(const BinaryTree *root)
{
  if (root == NULL) return;
  //一个队列保存当前依次遍历的层，一个队列保存遍历入队的下一层
  queue<const BinaryTree*> CurLevel;
  queue<const BinaryTree*> NextLevel;
  //再用一个栈来从低到高输出
  stack<queue<const BinaryTree*>> s;
  //首先将根节点入队列和栈
  CurLevel.push(root);
  //因为每次循环后都会将下一层节点的队列给当前层队列
  //所以若当前层节点为空时，说明二叉树已经遍历完了
  while (!CurLevel.empty())
  {
    //首先将当前层入栈
    s.push(CurLevel);
    //内层循环每次将当前层节点遍历完，并将下一层元素全部存入NextLevel队列
    while (!CurLevel.empty())
    {
      if (CurLevel.front()->left != NULL) NextLevel.push(CurLevel.front()->left);
      if (CurLevel.front()->right != NULL) NextLevel.push(CurLevel.front()->right);
      CurLevel.pop();
    }
    //将下一层节点的队列给当前层的队列
    CurLevel = NextLevel;
    //清空下一层的队列
    while (!NextLevel.empty())
      NextLevel.pop();
  }
  //通过栈依次输出即可
  while (!s.empty())
  {
    while (!s.top().empty())
    {
      cout << s.top().front()->data << " ";
      s.top().pop();
    }
    cout << endl;
    s.pop();
  }
}

暂时只想到这种解决办法，若有更好的方法，还望不吝指教。

后续补图。