二叉树的前序中序后序遍历(Java非递归实现)
前言
二叉树的非递归利用栈实现，栈的特性是先进后出，实现回溯
二叉树的节点定义
private static class TreeNode {
int data;
TreeNode leftChild;
TreeNode rightChild;
public TreeNode(int data) {
this.data = data;
}
}
前序遍历
前序遍历的输出顺序是根节点 -> 左子树 -> 右子树
public static void preOrderTraveralWithStack (TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode treeNode = node;
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
System.out.print(treeNode.data + " ");
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
treeNode = treeNode.rightChild;
}
}
}
中序遍历
中序遍历的输出顺序是左子树 -> 根节点 -> 右子树
public static void inOrderTraveralWithStack (TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode treeNode = node;
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
System.out.print(treeNode.data + " ");
treeNode = treeNode.rightChild;
}
}
}
后序遍历
后序遍历的输出顺序是左子树 -> 右子树 -> 根节点
利用栈stack1回溯记录前一节点，如果有左子树先压入栈stack1，如果有右子树后压入栈stack2，栈stack2作为辅助栈存储根节点 -> 右子树 -> 左子树，输出时利用栈先进后出的特性，逆序输出变成后序遍历的顺序左子树 -> 右子树 -> 根节点
public static void postOrderTraveralWithStack (TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>(); // 辅助栈 存储 根->右->左
TreeNode treeNode = node;
stack1.push(treeNode);
while (!stack1.isEmpty()) {
treeNode = stack1.pop();
stack2.push(treeNode);
if (treeNode.leftChild != null) {
stack1.push(treeNode.leftChild);
}
if (treeNode.rightChild != null) {
stack1.push(treeNode.rightChild);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().data + " ");
}
}
总结
大部分利用递归解决的问题，都可以利用栈解决，因为递归和栈都有回溯的特性
