二叉树的层次遍历

发布时间:2020-10-14 11:30:00
阅读量:42
作者:猎维人工智能培训
算法面试题

题目描述

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。


例如:

给定二叉树: [3,9,20,null,null,15,7],

   3

  / \

 9 20

   / \

  15  7

返回其层次遍历结果:

[

 [3],

 [9,20],

 [15,7]

]

分析与解法

节点的定义:

struct Node {

   Node *pLeft;

   Node *pRight;

   int data;

};

书上的解法

书上举出两个解法。第一个解法是用递归方式,搜寻并打印某一层的节点,再打印下一层的节点。这方法简单但时间效率不高(但不需要额外空间),因此书中亦提供了第二个解法。


书中第二个解法,使用vector容器来储存n个节点信息,并用一个游标变量last记录前一层的访问结束条件,实现如下:

void PrintNodeByLevel(Node* root) {

    vector vec; // 这里我们使用STL 中的vector来代替数组,可利用到其动态扩展的属性

    vec.push_back(root);

    int cur = 0;

    int last = 1;

    while(cur < vec.size()) {

         Last = vec.size(); // 新的一行访问开始,重新定位last于当前行最后一个节点的下一个位置

         while(cur < last) {

              cout << vec[cur] -> data << " "; // 访问节点

              if(vec[cur] -> lChild) // 当前访问节点的左节点不为空则压入

                  vec.push_back(vec[cur] -> lChild);

              if(vec[cur] -> rChild) // 当前访问节点的右节点不为空则压入,注意左右节点的访问顺序不能颠倒

                  vec.push_back(vec[cur] -> rChild);

              cur++;

         }

         cout << endl; // 当cur == last时,说明该层访问结束,输出换行符

    }

}

广度优先搜索

书中没有提及,本问题其实是以广度优先搜索(breath-first search, BFS)去遍历一个树结构。广度优先搜索的典型实现是使用队列(queue)。其伪代码如下:

enqueue(Q, root)

do

   node = dequeue(Q)

   process(node) //如把内容列印

   for each child of node

       enqueue(Q, child)

while Q is not empty

书上的解法,事实上也使用了一个队列。但本人认为,使用vector容器,较不直觉,而且其空间复杂度是O(n)。

如果用队列去实现BFS,不处理换行,能简单翻译伪代码为C++代码:

void PrintBFS(Node* root) {

   queue Q;

   Q.push(root);

   do {

       Node *node = Q.front();

       Q.pop();

       cout << node->data << " ";

       if (node->pLeft)

           Q.push(node->pLeft);

       if (node->pRight)

           Q.push(node->pRight);

   }

   while (!Q.empty());

}


本人觉得这样的算法实现可能比较清楚,而且空间复杂度只需O(m),m为树中最多节点的层的节点数量。最坏的情况是当二叉树为完整,m = n/2。

之后的难点在于如何换行。

本人的尝试之一

第一个尝试,利用了两个队列,一个储存本层的节点,另一个储存下层的节点。遍历本层的节点,把其子代节点排入下层队列。本层遍历完毕后,就可换行,并交换两个队列。

void PrintNodeByLevel(Node* root) {

   deque Q1, Q2;

   Q1.push_back(root);

   do {

       do {

           Node* node = Q1.front();

           Q1.pop_front();

           cout << node->data << " ";

           if (node->pLeft)

               Q2.push_back(node->pLeft);

           if (node->pRight)

               Q2.push_back(node->pRight);

       } while (!Q1.empty());

       cout << endl;

       Q1.swap(Q2);

   } while(!Q1.empty());

}

本实现使用deque而不是queue,因为deque才支持swap()操作。注意,swap()是O(1)的操作,实际上只是交换指针。

这实现要用两个循环(书上的实现也是),并且用了两个队列。能够只用一个循环、一个队列么?

本人的尝试之二

换行问题其实在于如何表达一层的结束。书上采用了游标,而第一个尝试则用了两个队列。本人想到第三个可行方案,是把一个结束信号放进队列里。由于使用queue,可以插入一个空指针去表示一层的遍历结束。

void PrintNodeByLevel(Node* root) {

   queue Q;

   Q.push(root);

   Q.push(0);

   do {

       Node* node = Q.front();

       Q.pop();

       if (node) {

           cout << node->data << " ";

           if (node->pLeft)

               Q.push(node->pLeft);

           if (node->pRight)

               Q.push(node->pRight);

       }

       else if (!Q.empty()) {

           Q.push(0);

           cout << endl;

       }

   } while (!Q.empty());

}


这个实现的代码很贴近之前的PrintBFS(),也只有一个循环。注意一点,当发现空指针(结束信号)时,要检查队列内是否还有节点,如果没有的话还插入新的结束信号,则会做成死循环。

测试代码

void Link(Node* nodes, int parent, int left, int right) {

   if (left != -1)

       nodes[parent].pLeft = &nodes[left];

 

   if (right != -1)

       nodes[parent].pRight = &nodes[right];

}

 

void main()

{

   Node test1[9] = { 0 };

    

   for (int i = 1; i < 9; i++)

       test1[i].data = i;

 

   Link(test1, 1, 2, 3);

   Link(test1, 2, 4, 5);

   Link(test1, 3, 6, -1);

   Link(test1, 5, 7, 8);

 

   PrintBFS(&test1[1]);

   cout << endl << endl;

 

   PrintNodeByLevel(&test1[1]);

   cout << endl;

}

 

更多资讯