二叉树的前序遍历非递归实现

算法与数据结构 2021-05-28 1956

描述

我们之前说了二叉树基础及二叉的几种遍历方式及练习题，今天我们来看一下二叉树的前序遍历非递归实现。

前序遍历的顺序是，对于树中的某节点，先遍历该节点，然后再遍历其左子树，最后遍历其右子树。

我们先来通过下面这个动画复习一下二叉树的前序遍历。

迭代遍历

我们试想一下，之前我们借助队列帮我们实现二叉树的层序遍历，

那么可不可以，也借助数据结构，帮助我们实现二叉树的前序遍历。

假设我们的二叉树为［1，2，3］。我们需要对其进行前序遍历。其遍历顺序为

当前节点 1，左孩子 2，右孩子 3。

这里可不可以用栈，帮我们完成前序遍历呢？

栈和队列的那些事

我们都知道栈的特性是先进后出，我们借助栈来帮助我们完成前序遍历的时候。

则需要注意的一点是，我们应该先将右子节点入栈，再将左子节点入栈。

这样出栈时，则会先出左节点，再出右子节点，则能够完成树的前序遍历。

我们用一句话对上图进行总结，当栈不为空时，栈顶元素出栈，如果其右孩子不为空，则右孩子入栈，其左孩子不为空，则左孩子入栈。还有一点需要注意的是，我们和层序遍历一样，需要先将 root 节点进行入栈，然后再执行 while 循环。

看到这里你已经能够自己编写出代码了，不信你去试试。

时间复杂度：O（n）需要对所有节点遍历一次

空间复杂度：O（n）栈的开销，平均为 O（logn）最快情况，即斜二叉树时为 O（n）

参考代码

class Solution {

public List《Integer》 preorderTraversal（TreeNode root） {

List《Integer》 list = new ArrayList《》（）;

Stack《TreeNode》 stack = new Stack《》（）;

if （root == null） return list;

stack.push（root）;

while （！stack.isEmpty（）） {

TreeNode temp = stack.pop（）;

if （temp.right ！= null） {

stack.push（temp.right）;

}

if （temp.left ！= null） {

stack.push（temp.left）;

}

//这里也可以放到前面

list.add（temp.val）;

}

return list;

}

Morris

Morris 遍历利用树的左右孩子为空（大量空闲指针），实现空间开销的极限缩减。这个遍历方式，稍微有那么一丢丢难理解，不过结合动图，也就一目了然，下面我们先看动画吧。

看完视频，是不是感觉自己搞懂了，又感觉自己没搞懂，哈哈，咱们继续往下看。

我们之前说的，Morris 遍历利用了树中大量空闲指针的特性，我们需要找到当前节点的左子树中的最右边的叶子节点，将该叶子节点的 right 指向当前节点。例如当前节点为2，其左子树中的最右节点为 9 ，则在 9 节点添加一个 right 指针指向 2。

其实上图中的 Morris 遍历遵循两个原则，我们在动画中也能够得出。

1.当 p1.left == null 时，p1 = p1.right。（这也就是我们为什么要给叶子节点添加 right 指针的原因）

2.如果 p1.left ！= null，找到 p1 左子树上最右的节点。（也就是我们的 p2 最后停留的位置），此时我们又可以分为两种情况，一种是叶子节点添加 right 指针的情况，一种是去除叶子节点 right 指针的情况。

如果 p2 的 right 指针指向空，让其指向 p1，p1向左移动，即 p1 = p1.left

如果 p2 的 right 指针指向 p1，让其指向空，（为了防止重复执行，则需要去掉 right 指针）p1 向右移动，p1 = p1.right。

这时你可以结合咱们刚才提到的两个原则，再去看一遍动画，并代入规则进行模拟，差不多就能完全搞懂啦。

下面我们来对动画中的内容进行拆解，

首先 p1 指向 root节点

p2 = p1.left，下面我们需要通过 p2 找到 p1的左子树中的最右节点。即节点 5，然后将该节点的 right 指针指向 root。并记录 root 节点的值。

向左移动 p1，即 p1 = p1.left

p2 = p1.left ，即节点 4 ，找到 p1 的左子树中的最右叶子节点，也就是 9，并将该节点的 right 指针指向 2。

继续向左移动 p1，即 p1 = p1.left，p2 = p1.left。也就是节点 8。并将该节点的 right 指针指向 p1。

我们发现这一步给前两步是一样的，都是找到叶子节点，将其 right 指针指向 p1，此时我们完成了添加 right 指针的过程，下面我们继续往下看。

我们继续移动 p1 指针，p1 = p1.left。p2 = p.left。此时我们发现 p2 == null，即下图此时我们需要移动 p1，但是不再是 p1 = p1.left 而是 p1 = p1.right。也就是 4，继续让 p2 = p1.left。此时则为下图这种情况

此时我们发现 p2.right ！= null 而是指向 4，说明此时我们已经添加过了 right 指针，所以去掉 right 指针，并让 p1 = p1.right

下面则继续移动 p1 ，按照规则继续移动即可，遇到的情况已经在上面做出了举例，所以下面我们就不继续赘述啦，如果还不是特别理解的同学，可以再去看一遍动画加深下印象。时间复杂度 O（n），空间复杂度 O（1）下面我们来看代码吧。

代码

class Solution {

public List《Integer》 preorderTraversal（TreeNode root） {

List《Integer》 list = new ArrayList《》（）;

if （root == null） {

return list;

}

TreeNode p1 = root; TreeNode p2 = null;

while （p1 ！= null） {

p2 = p1.left;

if （p2 ！= null） {

//找到左子树的最右叶子节点

while （p2.right ！= null && p2.right ！= p1） {

p2 = p2.right;

}

//添加 right 指针，对应 right 指针为 null 的情况

if （p2.right == null） {

list.add（p1.val）;

p2.right = p1;

p1 = p1.left;

continue;

}

//对应 right 指针存在的情况，则去掉 right 指针

p2.right = null;

} else {

list.add（p1.val）;

}

//移动 p1

p1 = p1.right;

}

return list;

}

原文标题：把二叉树揉碎（二）

文章出处：【微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。

责任编辑：haq

打开APP阅读更多精彩内容