迭代模拟递归
public class BinaryTreeStackPrinter {
public static void iterationPrint(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
iterationPrint(stack);
}
private static void iterationPrint(Stack<TreeNode> stack) {
// newStackFrame == true 表示当前有新节点入栈
boolean newStackFrame = true;
// lastVisisted 记录最近一次从栈中弹出的节点，避免重复入栈
TreeNode lastVisited = new TreeNode(-1);
while (!stack.isEmpty()) {
TreeNode root = stack.peek();
if (newStackFrame) {
System.out.println(root.val + " 【入栈】 | " + stack);
}
// 因为先访问左子树，所以如果左子树 or 右子树被访问过，说明左子树已经被访问过了
boolean leftNodeVisited = (root.left == lastVisited || root.right == lastVisited);
// 左子树不为空，且没有被访问过，才压栈
if (root.left != null && !leftNodeVisited) {
stack.push(root.left);
newStackFrame = true;
continue; // 通过 continue 模拟递归调用
}
boolean rightNodeVisited = (root.right == lastVisited);
// 右子树不为空，且没有被访问过，才压栈
if (root.right != null && !rightNodeVisited) {
stack.push(root.right);
newStackFrame = true;
continue; // 通过 continue 模拟递归调用
}
root = stack.pop();
System.out.println("----------" + root.val + "] 【出栈】 | " + stack);
// 弹出栈中元素，会回退到上一个压栈元素，因此不会创建一个新的栈帧
newStackFrame = false;
// 记录最后一个弹出的元素，避免刚出栈又重新入栈
lastVisited = root;
}
}
}
三种遍历方式
public class BinaryTreeStackPrinter {
public static void iterationPrint(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
iterationPrint(stack);
}
private static void iterationPrint(Stack<TreeNode> stack) {
// newStackFrame == true 表示当前有新节点入栈
boolean newStackFrame = true;
// lastVisisted 记录最近一次从栈中弹出的节点，避免重复入栈
TreeNode lastVisited = new TreeNode(-1);
while (!stack.isEmpty()) {
TreeNode root = stack.peek();
if (newStackFrame) {
System.out.println(root.val + " 【入栈】 | " + stack);
// System.out.println("【前序遍历】" + root.val);
}
// 因为先访问左子树，所以如果左子树 or 右子树被访问过，说明左子树已经被访问过了
boolean leftNodeVisited = (root.left == lastVisited || root.right == lastVisited);
// 左子树不为空，且没有被访问过，才压栈
if (root.left != null && !leftNodeVisited) {
stack.push(root.left);
newStackFrame = true;
continue; // 通过 continue 模拟递归调用
}
boolean rightNodeVisited = (root.right == lastVisited);
if (!rightNodeVisited) {
// System.out.println("【中序遍历】" + root.val);
}
// 右子树不为空，且没有被访问过，才压栈
if (root.right != null && !rightNodeVisited) {
stack.push(root.right);
newStackFrame = true;
continue; // 通过 continue 模拟递归调用
}
root = stack.pop();
System.out.println("----------" + root.val + "] 【出栈】 | " + stack);
// System.out.println("【后序遍历】" + root.val);
// 弹出栈中元素，会回退到上一个压栈元素，因此不会创建一个新的栈帧
newStackFrame = false;
// 记录最后一个弹出的元素，避免刚出栈又重新入栈
lastVisited = root;
}
}
}
测试类：
public class BinaryTreeDemo {
public static void main(String[] args) {
TreeNode root = new BinaryTreeBuilder(3, 0.6, 0.6).build();
BinaryTreePrinter.print(root);
String prefixAndSuffix = String.join("", Collections.nCopies(20, "*"));
System.out.println(prefixAndSuffix + "【递归遍历】" + prefixAndSuffix);
BinaryTreeStackPrinter.recursivePrint(root);
System.out.println();
System.out.println(prefixAndSuffix + "【迭代遍历】" + prefixAndSuffix);
BinaryTreeStackPrinter.iterationPrint(root);
}
}
- 前序遍历输出：
maxLevel: 3
level[1] 节点宽度[ 16]===| 1
===| ┌───┴───┐
level[2] 节点宽度[ 8]===| 2 5
===| ┌─┴─┐ ┌─┘
level[3] 节点宽度[ 4]===| 3 4 6
********************【递归遍历】********************
1 【入栈】 | [1]
【前序遍历】1
2 【入栈】 | [1, 2]
【前序遍历】2
3 【入栈】 | [1, 2, 3]
【前序遍历】3
----------3【出栈】 | [1, 2]
4 【入栈】 | [1, 2, 4]
【前序遍历】4
----------4【出栈】 | [1, 2]
----------2【出栈】 | [1]
5 【入栈】 | [1, 5]
【前序遍历】5
6 【入栈】 | [1, 5, 6]
【前序遍历】6
----------6【出栈】 | [1, 5]
----------5【出栈】 | [1]
----------1【出栈】 | []
********************【迭代遍历】********************
1 【入栈】 | [1]
【前序遍历】1
2 【入栈】 | [1, 2]
【前序遍历】2
3 【入栈】 | [1, 2, 3]
【前序遍历】3
----------3] 【出栈】 | [1, 2]
4 【入栈】 | [1, 2, 4]
【前序遍历】4
----------4] 【出栈】 | [1, 2]
----------2] 【出栈】 | [1]
5 【入栈】 | [1, 5]
【前序遍历】5
6 【入栈】 | [1, 5, 6]
【前序遍历】6
----------6] 【出栈】 | [1, 5]
----------5] 【出栈】 | [1]
----------1] 【出栈】 | []
- 中序遍历输出：
maxLevel: 3
level[1] 节点宽度[ 16]===| 1
===| ┌───┴───┐
level[2] 节点宽度[ 8]===| 2 4
===| ┌─┘ └─┐
level[3] 节点宽度[ 4]===| 3 5
********************【递归遍历】********************
1 【入栈】 | [1]
2 【入栈】 | [1, 2]
3 【入栈】 | [1, 2, 3]
【中序遍历】3
----------3【出栈】 | [1, 2]
【中序遍历】2
----------2【出栈】 | [1]
【中序遍历】1
4 【入栈】 | [1, 4]
【中序遍历】4
5 【入栈】 | [1, 4, 5]
【中序遍历】5
----------5【出栈】 | [1, 4]
----------4【出栈】 | [1]
----------1【出栈】 | []
********************【迭代遍历】********************
1 【入栈】 | [1]
2 【入栈】 | [1, 2]
3 【入栈】 | [1, 2, 3]
【中序遍历】3
----------3] 【出栈】 | [1, 2]
【中序遍历】2
----------2] 【出栈】 | [1]
【中序遍历】1
4 【入栈】 | [1, 4]
【中序遍历】4
5 【入栈】 | [1, 4, 5]
【中序遍历】5
----------5] 【出栈】 | [1, 4]
----------4] 【出栈】 | [1]
----------1] 【出栈】 | []
- 后序遍历输出：
maxLevel: 3
level[1] 节点宽度[ 16]===| 1
===| ┌───┴───┐
level[2] 节点宽度[ 8]===| 2 5
===| ┌─┴─┐ ┌─┘
level[3] 节点宽度[ 4]===| 3 4 6
********************【递归遍历】********************
1 【入栈】 | [1]
2 【入栈】 | [1, 2]
3 【入栈】 | [1, 2, 3]
----------3【出栈】 | [1, 2]
【后序遍历】3
4 【入栈】 | [1, 2, 4]
----------4【出栈】 | [1, 2]
【后序遍历】4
----------2【出栈】 | [1]
【后序遍历】2
5 【入栈】 | [1, 5]
6 【入栈】 | [1, 5, 6]
----------6【出栈】 | [1, 5]
【后序遍历】6
----------5【出栈】 | [1]
【后序遍历】5
----------1【出栈】 | []
【后序遍历】1
********************【迭代遍历】********************
1 【入栈】 | [1]
2 【入栈】 | [1, 2]
3 【入栈】 | [1, 2, 3]
----------3] 【出栈】 | [1, 2]
【后序遍历】3
4 【入栈】 | [1, 2, 4]
----------4] 【出栈】 | [1, 2]
【后序遍历】4
----------2] 【出栈】 | [1]
【后序遍历】2
5 【入栈】 | [1, 5]
6 【入栈】 | [1, 5, 6]
----------6] 【出栈】 | [1, 5]
【后序遍历】6
----------5] 【出栈】 | [1]
【后序遍历】5
----------1] 【出栈】 | []
【后序遍历】1
网友评论