前言

二叉树的非递归利用栈实现，栈的特性是先进后出，实现回溯

二叉树的节点定义

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 + " ");}}

总结

大部分利用递归解决的问题，都可以利用栈解决，因为递归和栈都有回溯的特性