目录
递归遍历
前序递归遍历
中序和后序递归遍历
非递归遍历
非递归前序遍历
非递归中序遍历
标记法
直接干
非递归后序遍历
标记法
reverse法
递归遍历
前序递归遍历
首先从简单的开始
class Solution {
public List preorderTraversal(TreeNode root) {
List ret = new ArrayList();
preorderTraversalRecur(root,ret);
return ret;
}
void preorderTraversalRecur(TreeNode node, List ret){
if(node==null){ return;}
ret.add(node.val);//将 中 写入答案
preorderTraversalRecur(node.left,ret); //对 左子树 前序遍历
preorderTraversalRecur(node.right,ret);//对 右子树 前序遍历
}
}
中序后序只需要换一下语句顺序即可：
中序和后序递归遍历
class Solution {
public List inorderTraversal(TreeNode root) {
List ret = new ArrayList<>();
inorderTraversalRecur(root,ret);
return ret;
}
void inorderTraversalRecur(TreeNode node , List ret){
if(node==null){ return;}
inorderTraversalRecur(node.left,ret);//对 左子树 中序遍历
ret.add(node.val);//将 中 写入答案
inorderTraversalRecur(node.right,ret);//对 右子树 中序遍历
}
}
class Solution {
public List postorderTraversal(TreeNode root) {
List ret = new ArrayList();
postorderTraversalRecur( root, ret);
return ret;
}
void postorderTraversalRecur(TreeNode node, List ret){
if(node==null) { return;}
postorderTraversalRecur(node.left, ret);//对 左子树 后序遍历
postorderTraversalRecur(node.right, ret);//对 右子树 后序遍历
ret.add(node.val);//将 中 写入答案
}
}
非递归遍历
在这个基础上我们可以开始非递归方法
大的思维框架是：
递归的实现本质 是每次调用函数就会生成一个“栈帧”（stack frame） 保存着这个函数的相关信息（局部变量 运行到第几行了 之类的）
注：一个栈帧对应一个未运行完的函数；当某一个函数被调用一次时，就会产生一个栈帧(记录着该函数的相关信息)，并入栈;当该函数运行完毕之后，其对应的栈帧会出栈。注：函数的一次调用就会产生一个对应的栈帧，而不是一个函数本身对应一个栈帧；如：递归调用就会产生无数个栈帧。
原文链接：https://blog.csdn.net/justry_deng/article/details/86761833
我们用非递归的方式做 如果采取和递归同样的思路
其实是要把这个栈显式的写出来 模拟记录函数的信息 以达到类似的效果
非递归前序遍历
再复习一下递归法的顺序：
class Solution {
public List preorderTraversal(TreeNode root) {
List ret = new ArrayList();
preorderTraversalRecur(root,ret);
return ret;
}
void preorderTraversalRecur(TreeNode node, List ret){
if(node==null){ return;}
ret.add(node.val);//1 将 中 写入答案
preorderTraversalRecur(node.left,ret); //2 对 左子树 前序遍历
preorderTraversalRecur(node.right,ret);//3 对 右子树 前序遍历
}
}
我们用栈的大致思路应该有了：
-1 首先要有个 栈stack 是模拟栈帧 保存我们未来要做的事情的
0 首先要有个 指针p 指向当前我们处理的节点（也可以说是函数运行的位置 相当于递归法的入参 node) 一开始p=root
循环开始（递归改循环 结束条件是stack.isEmpty() && p==null 意思是没有未完成函数 当前函数也完成了）
if(p==null) { return应该改成 p=stack.pop() 因为栈里面存了我们下一个“要回到的函数”}
1 将 中 写入答案 这个不用改
2 对 左子树 前序遍历 这个我们应该要将p指向p.left（但如果直接这么做 我们会丢失第3步）
3 对 右子树 前序遍历 为了记录我们还没做第3步呢 所以我们应该先将 p.right入栈
循环结束
现在的思路：
stack
p=root
while(!stack.isEmpty() || p!=null){
if(p==null){ p=stack.pop()}
将 中p.val 写入答案
记录我们之后要 对 右子树 前序遍历 ： 将 右孩p.right入栈
对 左子树 前序遍历 ：p=p.left
}
代码：
class Solution {
public List preorderTraversal(TreeNode root) {
List ret =new ArrayList<>();
Stack stack=new Stack<>();
TreeNode p=root;
while(!stack.isEmpty() || p!=null){ //结束条件为 栈里没有未完成函数 当前函数也完成了
if(p==null){
p=stack.pop();//回到上一个未完成的函数
}
else{
ret.add(p.val);//将 中 写入答案
stack.push(p.right);//记录我们之后要 对 右子树 前序遍历
p=p.left;//对 左子树 前序遍历
}
}
return ret;
}
}
如果喜欢 我们还可以写出跟递归法对应得更好的代码：
class Solution {
public List preorderTraversal(TreeNode root) {
List ret =new ArrayList<>();
Stack stack=new Stack<>();
stack.add(root);
TreeNode p=null;
while(!stack.isEmpty() ){
p=stack.pop();//函数开始 先读入参
if(p==null) continue;//如果p==null 回到上一个需要执行的函数
ret.add(p.val);//将 中 写入
stack.add(p.right);//记录以后要对 右子 进行前序遍历
stack.add(p.left); //记录以后要对 左子 进行前序遍历
}
return ret;
}
}
非递归中序遍历
复习一下递归法的顺序
class Solution {
public List inorderTraversal(TreeNode root) {
List ret = new ArrayList<>();
inorderTraversalRecur(root,ret);
return ret;
}
void inorderTraversalRecur(TreeNode node , List ret){
if(node==null){ return;}
inorderTraversalRecur(node.left,ret);//对 左子树 中序遍历
ret.add(node.val);//将 中 写入答案
inorderTraversalRecur(node.right,ret);//对 右子树 中序遍历
}
}
以下介绍两种非递归中序遍历：标记法 和 直接法
标记法 思路更为通用 其实前中后序都可以用 和递归法思路对应更清楚 问题就是要引入一个标记
直接法 好处就是不需要标记（废话） 但是思路不那么通用 不好移植到其他问题上
标记法
我们用栈的大致思路应该有了：
-1 首先要有个 栈stack 是模拟栈帧 保存我们未来要做的事情的
0 首先要有个 指针p 指向当前我们处理的节点（也可以说是函数运行的位置 相当于递归法的入参 node) 一开始p=root
循环开始（递归改循环 结束条件是stack.isEmpty() && p==null 意思是没有未完成函数 当前函数也完成了）
if(p==null) { return应该改成 p=stack.pop() 因为栈里面存了我们下一个“要回到的函数”}
1 对 左子树 中序遍历 （直接p=p.left 即可 但是直接这么做我们会损失第2，3步）
2 将 中 写入答案 （所以我们先得把 中 入栈了）
3 对 右子树 中序遍历 （所以我们先得把 右子 入栈了 。而且入栈顺序是 ”右子 中“ 出栈顺序才能是”中 右子“）
循环结束
现在的思路：
stack
p=root
while(!stack.isEmpty() || p!=null){
if(p==null){ p=stack.pop() }
记录我们之后要对 右子树 中序遍历： 右子入栈
记录我们之后要将 中 写入答案 ： 中入栈
对 左子树 中序遍历 ：p=p.left
}
看起来和前面差不多 但是问题出现了！
我们把 右子 和 中 都入栈了，但是我们想做的却是两件不一样的事情 一个是要对子树进行遍历 一个是要把节点值写入答案 怎么办？
所以我们需要用标记法 引入一个标记来区分 中 和 右子
标记的具体方式有很多种 比如
直接修改节点定义 加一个boolean
包装一下节点 加一个boolean
加一个数组或者hashSet或者别的什么东西 记录谁isVisited
在中的前面插一个null
更改一下中 或者 右子 的数据类型
节点放入栈之后，紧接着放入一个空指针作为标记
示例代码直接修改了节点定义 比较偷懒 大家自己选择比较好的方法
现在的思路：
stack
p=root
while(!stack.isEmpty() || p!=null){
if(p==null){ 回到上一个未完成的事情： p=stack.pop() }
else if( p.isVisited){ //要将 中 写入答案
将 中 写入答案
回到上一个未完成的事情 ： p=stack.pop()
}
else{//默认情况 是要对p中序遍历
记录我们之后要对 右子树 中序遍历： 右子入栈 默认无标记
记录我们之后要将 中 写入答案 ： 中入栈 标记为visited
对 左子树 中序遍历 ：p=p.left
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
boolean isVisited; //加了一个isVisited
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public List inorderTraversal(TreeNode root) {
// if(root==null) return null;
List ret = new ArrayList<>();
Stack stack = new Stack<>();
TreeNode p = root;
while(!stack.isEmpty() || p!=null){
if(p==null) {
p=stack.pop();//回到上一个未完成的事情
}
else if(p.isVisited){// 要将 中 写入答案
ret.add(p.val);//将 中 写入答案
p=stack.pop();//回到上一个未完成的事情
}
else{
stack.push(p.right);//记录我们之后要对 右子树 中序遍历：右子入栈 默认无标记
stack.push(p);//记录我们之后要将 中 写入答案 ： 中入栈
p.isVisited=true;// 标记为visited
p=p.left;//对 左子树 中序遍历 ：p=p.left
}
}
return ret;
}
}
更加对应递归的代码：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
boolean isVisited; //加了一个isVisited
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public List inorderTraversal(TreeNode root) {
// if(root==null) return null;
List ret = new ArrayList<>();
Stack stack = new Stack<>();
stack.add(root);
TreeNode p =null;
while(!stack.isEmpty()){
p=stack.pop();//函数开始 读入参
if(p==null) continue;// 如果p==null 去读栈顶下一个要运行的函数
else if(p.isVisited){// 要将 中 写入答案
ret.add(p.val);//将 中 写入答案
}
else{//默认情况
stack.push(p.right);//记录我们之后要对 右子树 中序遍历：右子入栈 默认无标记
stack.push(p);//记录我们之后要将 中 写入答案 ： 中入栈
p.isVisited=true;// 标记为visited
stack.push(p.left);//记录我们之后要对 左子树 中序遍历：右子入栈 默认无标记
}
}
return ret;
}
}
直接干
//普遍情况 首先一路向左 把中入栈（可以理解成递归函数运行到 2 把中写入答案 之前 但是这里我只需要记录中
//特殊情况 直到左下没了 回到上一个中 往右走一步（ 也就是把递归函数后半截运行完了
2 把中写入答案 3 对右子树进行中序递归
有能力脑里过一下整个过程 就知道这是正确的 可惜这种写法通用性不强 每个题都得这样想一遍 费脑
class Solution {
public List inorderTraversal(TreeNode root) {
List ret = new ArrayList<>();
Stack stack= new Stack<>();
TreeNode cur=root;
while(cur!=null || !stack.isEmpty()){
if(cur != null){// 普遍情况 首先一路向左 把中入栈
stack.push(cur);
cur=cur.left;
}
else{// 特殊情况 直到左下没了 回到上一个中 往右走一步（然后比较可能回到普遍情况
cur=stack.pop();
ret.add(cur.val);
cur=cur.right;
}
}
非递归后序遍历
同样给大家介绍两种方法 ： 标记法和reverse法
标记法大家应该已经比较了解了 直接上代码吧~
class TreeNode {
int val;
TreeNode left;
TreeNode right;
boolean isVisited; //加了一个isVisited
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public List postorderTraversal(TreeNode root) {
List ret = new ArrayList<>();
Stack stack = new Stack<>();
stack.add(root);
TreeNode p =null;
while(!stack.isEmpty()){
p=stack.pop();//函数开始 读入参
if(p==null) continue;// 如果p==null 去读栈顶下一个要运行的函数
else if(p.isVisited){// 要将 中 写入答案
ret.add(p.val);//将 中 写入答案
}
else{//默认情况
stack.push(p);//记录我们之后要将 中 写入答案 ： 中入栈
p.isVisited=true;// 标记为visited
stack.push(p.right);//记录我们之后要对 右子树 后序遍历：右子入栈 默认无标记
stack.push(p.left);//记录我们之后要对 左子树 后序遍历：右子入栈 默认无标记
}
}
return ret;
}
}
reverse法
后序：左右中
但是用栈很难写（根源在于访问节点和写入ans不是同一时间 你得想办法分清楚这是对应递归法的哪个步骤）
要么要用标记法 要么分叉有三个 太复杂了
这里我们有一个巧妙的方法 ：中右左 然后将答案reverse 因为中右左很容易用栈做
class Solution {
public List postorderTraversal(TreeNode root) {
linkedList ans = new linkedList<>();
Stack stack = new Stack<>();
TreeNode p=root;
//后序：左右中 但是我们的做法是：中右左 然后reverse
while(!stack.isEmpty() || p!=null){
if(p==null){// 特殊情况 p为空 取栈顶
p=stack.pop();
}
else{// 一般情况 左子入栈 中间写入ans 继续往右子走
ans.addFirst(p.val); //在这里addFirst相当于把答案reverse了
stack.push(p.left);
p=p.right;
}
}
return ans;
}
}
