作者：敲代码の流川枫
博客主页：流川枫的博客
专栏：和我一起学java
语录：Stay hungry stay foolish
Apifox = Postman + Swagger + Mock + JMeter。集接口文档工具、接口Mock工具、接口自动化测试工具、接口调试工具于一体,提升 10 倍研发效率
文章目录
二叉树用递归来进行遍历是很简单的，就几行代码，今天总结一下如何进行非递归遍历
1.前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
思路
用迭代的方式实现递归函数解法，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同
代码
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> ret = new ArrayList<>();
TreeNode cur = root;
//最外层循环是最后才加上去的，开始写的时候想不到这个循环条件
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
System.out.print(cur.val+" ");
ret.add(cur.val);
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
return ret;
}
}
时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
2.中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
代码
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
ret.add(top.val);
cur = top.right;
}
return ret;
}
}
3.后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历。
思路
和前面遍历思路相同，只需要注意根节点入表的判断条件，这里用了prev标记，避免死循环
代码
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
//当前节点
TreeNode cur = root;
//用来标记上一个被打印的节点
TreeNode prev = null;
Stack<TreeNode> stack = new Stack<>();
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
//或者后面表示已经被打印过了，如果top.right打印过了，
就继续弹出top，而不是cur = top.right陷入死循环
if(top.right == null || top.right == prev){
ret.add(top.val);
stack.pop();
prev = top;
}else{
cur = top.right;
}
}
return ret;
}
}
时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次
空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(\log n)，最坏情况下树呈现链状，为 O(n)
原文链接: https://blog.csdn.net/chenchenchencl/article/details/127258398