# 二叉树的遍历 (迭代法)

Bianry Tree 的遍历分为中序，前序和后序。遍历顺序分别为：中-左-右，左-中-右，左-右-中。

``````public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}``````

#### 中序遍历 左-中-右

``````class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>(); // Store the traversal result
if (root == null) {
return res;
}

TreeNode curr = root; // Pointer to traverse the tree
Stack<TreeNode> stack = new Stack<>();
while (curr != null || !stack.isEmpty()) {
while (curr != null) { // Keep push the left node into stack
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right; // Move to the right node
}

return res;
}
}``````

#### 前序遍历 中-左-右

``````class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>(); // Store the traversal result
if (root == null) {
return res;
}

Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;

while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
curr = stack.pop(); // 节点为空，父节点出栈
curr = curr.right;
}
}
return res;
}
}``````

``````class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>(); // Store the traversal result
if (root == null) {
return res;
}

Stack<TreeNode> stack = new Stack<>();
stack.push(root);

while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
if (curr == null) {
continue;
}
stack.push(curr.right);
stack.push(curr.left);
}
return res;
}
}``````

1个月前 评论
Borris （楼主） 1个月前
zyfsuzy （作者） 1个月前

52

4

11

16