二叉树的前序、中序、后序遍历 非递归解法
数据结构二叉树遍历基础，递归解法在很早之前的博客就以C语言的形式总结了，这篇博文聚焦非递归解法。二叉树的前序、中序、后序遍历都可以借助栈来实现，因为递归本质也是靠栈来实现的，中序遍历还有一种比较难想的镜像法。
前序遍历 leetcode 144. Binary Tree Preorder Traversal
直接使用栈，入栈顺序先右子树在左子树。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList();
if(root == null) return res;
Stack<TreeNode> stack = new Stack();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if(cur.right != null) {
stack.push(cur.right);
}
if(cur.left != null) {
stack.push(cur.left);
}
}
return res;
}
}中序遍历 leetcode 94. Binary Tree Inorder Traversal
维护一个cur指针和栈，cur指针指向当前处理的节点，栈中存将要处理的节点，二者任意为空结束循环。
当前节点入栈，不断往左子树走并入栈，没有左子树之后(即到达最左端节点)出栈，节点值加入结果集，走一次右子树。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return new ArrayList<Integer>();
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while(curr != null || !stack.isEmpty()) {
while(curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}镜像法
简而言之：
- 初始化curr为根节点，
while循环条件curr不为null。 - 如果curr没有左子树，将curr.val加入结果集，并走向右子树
- 如果curr有左子树，将curr设置为左子树的最右端结点，并走向左子树
这种解法其实改变了树的结构，因而不推荐。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return new ArrayList<Integer>();
List<Integer> res = new ArrayList<>();
TreeNode curr = root, pre, temp;
while(curr != null) {
if(curr.left == null) {
res.add(curr.val);
curr = curr.right;
} else {
pre = curr.left;
while(pre.right != null) {
pre = pre.right;
}
pre.right = curr;
temp = curr;
curr = curr.left;
temp.left = null;
}
}
return res;
}
}后序遍历 leetcode 145. Binary Tree Postorder Traversal
直接使用栈，入栈顺序先左子树后右子树(跟前序遍历相反，想一想为什么)，逆序加入结果集(想一想为什么)。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList();
if(root == null) return res;
Stack<TreeNode> stack = new Stack();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(0, cur.val);
if(cur.left != null) {
stack.push(cur.left);
}
if(cur.right != null) {
stack.push(cur.right);
}
}
return res;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-11-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录