在二叉树的非递归遍历上有很多种方法,但如果想要统一用一种通用方式来实现三者的非递归遍历还是很酷的.
树的结构
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
递归遍历
递归遍历很简单,这是leetcode144的题
class Solutiont144 {
ArrayList<Integer> res = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root != null) {
//递归模式只需要改变res.add的位置
res.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return res;
}
}
非递归遍历
借用Guide这个类,我习惯称之为"指令",在栈中压入一个"操作".
class generalPrintTree {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
Stack<Guide> path = new Stack<>();
path.push(new Guide(0, root));
while (!path.isEmpty()) {
Guide cur = path.pop();
if (cur.node == null) continue;
if (cur.ope == 1) { //当前指令是要输出,则输出(放到res里)
res.add(cur.node.val);
} else { //当前指令是要遍历这个node的子节点
// 核心代码 ope = 1放在最后是前序, 1放在中间是中序, 1放在第一行是后序, 交换right和left位置可以是其他遍历方式
path.push(new Guide(0, cur.node.right));
path.push(new Guide(0, cur.node.left));
path.push(new Guide(1, cur.node));
}
}
return res;
}
class Guide {
//Guide 可以认为是一个指令,这个指令里存有操作符ope 和node节点
int ope = 0; //0 ->visit, 1 ->print
TreeNode node;
public Guide(int ope, TreeNode node) {
this.ope = ope;
this.node = node;
}
}
}
以前序遍历为例:
image.png
而中序,后续遍历只要换核心的三行代码顺序就行了.准确的来说，根据遍历顺序倒序替换这三行即可
前序（根左右）
path.push(new Guide(0, cur.node.right));
path.push(new Guide(0, cur.node.left));
path.push(new Guide(1, cur.node));
中序（左根右）
path.push(new Guide(0, cur.node.right));
path.push(new Guide(1, cur.node));
path.push(new Guide(0, cur.node.left));
后序（左右根）
path.push(new Guide(1, cur.node));
path.push(new Guide(0, cur.node.right));
path.push(new Guide(0, cur.node.left));
规律很简单,因为是入栈操作,所以从后往前根据遍历顺序放这三行代码顺序即可
