二叉树的下一个节点

一、背景

前面讲解了《前序、中序、后续构造二叉树》，今天来讲解另一个问题：怎么构造二叉树每层节点的下一个节点。

二、问题

什么叫做二叉树每层节点的下一个节点呢？

可以看下图，是一个标准的二叉树。

每个节点有一个指向下一个右侧的节点指针，如果没有下一个，这个指针的值就为NULL。

看了这个图，大家应该就明白这篇文章的问题是什么了。

三、标准二叉树

我们先来看看对于标准二叉树，怎么构造同层的下一个节点指针。

仔细看图，可以发现图分两部分：一个是两个子树递归完成这个操作，一个是左子树的最右边指向右子树的最左边。

所以我们实现两个函数即可：一个是对一个树进行构造，一个是左子树和右子树进行构造。

四、普通二叉树

对于标准的二叉树，完成同层下一个节点的构造很简单。
但是对于普通的二叉树，就会遇到各种各样的问题。

比如对于下面的二叉树，我们不知道左子树的某一层最右边是哪个了。

实际应该这样连接。
而且，有一个更打击人的提示是：二叉树某一层的最左边也不是很容易确定。

面对这个问题，可以想到的第一个方法是 BFS。
我们使用队列广度优先搜索，每搜索一层，记录当前层的个数。
这样就能一层层的来进行构造下一个节点了。

但是，我们看下题的要求，会发现要求使用常数的额外空间。
所以我们就需要观察这道题来找相关特征，从而尝试去找突破口。

假设我们第n层已经全部找到下一个节点了。
我们能不能利用第n层的信息来快速找到第n+1层的节点了。

原来还真可以。
我们只需要保存第n层的第一个节点，然后通过遍历next可以找到第n+1层的第一个节点。
之后继续遍历next，就可以找到下一个第n+1层的节点，然后串起来即可。

五、最后

好了，这篇文章教大家怎么给一个二叉树构造每个节点的下一个节点。
标准二叉树主要学习递归，而普通二叉树，则有点难度了，你想到了吗？

-EOF-