数据结构二叉树遍历基础,递归解法在很早之前的博客就以C语言的形式总结了,这篇博文聚焦非递归解法。二叉树的前序、中序、后序遍历都可以借助栈来实现,因为递归本质也是靠栈来实现的,中序遍历还有一种比较难想的镜像法。
直接使用栈,入栈顺序先右子树在左子树。
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;
}
}
维护一个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;
}
}
简而言之:
while
循环条件curr不为null。这种解法其实改变了树的结构,因而不推荐。
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;
}
}
直接使用栈,入栈顺序先左子树后右子树(跟前序遍历相反,想一想为什么),逆序加入结果集(想一想为什么)。
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;
}
}