1. 前言
前文我们实现了二叉树前中后三种遍历方式的递归版本，非常简单. 接下来我们来实现一下其迭代版本.
2. 二叉树的前序遍历
(1). 题
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[1,2]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
(2). 思路
递归调用系统栈，迭代算法自己构造一个栈来模拟. cur指针指向根节点，while循环，条件只要cur不为空并且栈不为空，不断将元素添加到数组中(根)，直到访问到最左的叶子节点(左). 此时将其从栈弹出，访问右节点(右). 如果该右节点为空，则继续弹栈，访问弹栈出的节点右节点.不断继续此过程.
(3). 解
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
TreeNode p;
while (cur != null || !stack.isEmpty()){
if (cur != null) {
stack.push(cur);
list.add(cur.val);
cur = cur.left;
} else {
p = stack.pop();
cur = p.right;
}
}
return list;
}
}3. 二叉树的中序遍历
(1). 题
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
(2). 思路
while循环开始，如果cur不为null则一直压栈(左)，直到cur为null，弹栈，并访问该节点(根)，继续讨论该节点的右孩子(右). 继续弹栈，该节点的左孩子部分已经完成，访问该节点的值，继续讨论其右孩子.直到循环结束.
(3). 解
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
TreeNode p;
while (cur != null || !stack.isEmpty()){
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
p = stack.pop();
list.add(p.val);
cur = p.right;
}
}
return list;
}
}4. 二叉树的后序遍历
(1). 题
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
(2). 思路
思路如下.
(3). 解
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> al = new ArrayList<>();
if (root == null) {
return al;
}
TreeNode cur = root;
TreeNode pop = null;
Deque<TreeNode> stack = new LinkedList<>();
while (cur != null || !stack.isEmpty()){
//只要cur不为null, 一直访问左节点, 并不断入栈
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
//此时栈顶元素的左孩子为null 即其左孩子无需处理
TreeNode peek = stack.peek();
//peek.right == null表明栈顶元素的右孩子无需处理
//peek.right == pop表明栈顶元素的右孩子已经处理完毕
if (peek.right == null || peek.right == pop){
//访问该栈顶元素, 并弹出
al.add(peek.val);
//记录处理的节点
pop = stack.pop();
} else {
//else表明该栈顶元素的右孩子待处理, 则cur = peek.right
cur = peek.right;
}
}
}
return al;
}
}
