二叉树是一种常见的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的每个节点包含一个值以及指向其左子节点和右子节点的指针。
定义一个二叉树类
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(TreeNode left, int val, TreeNode right) {
this.left = left;
this.val = val;
this.right = right;
}
}
递归实现
前序遍历
static void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.val); // 值
preOrder(node.left); // 左
preOrder(node.right); // 右
}
中序遍历
static void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left); // 左
System.out.println(node.val); // 值
inOrder(node.right); // 右
}
后序遍历
static void postOrder(TreeNode node) {
if (node == null) {
return;
}
postOrder(node.left); // 左
postOrder(node.right); // 右
System.out.println(node.val); // 值
}
非递归实现
使用栈来记录来时的路。
当前节点不为null时，将当前节点的值输出并将其压入栈中，然后继续处理其左子节点；当当前节点为null时，从栈中弹出节点并处理其右子节点。
前序
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 代表当前节点
while (curr != null || !stack.isEmpty()) {
if(curr != null) {
System.out.println(curr.val);
stack.push(curr); // 压入栈，为了记住回来的路
curr = curr.left;
} else {
TreeNode pop = stack.pop();
//System.out.println(pop.val);
curr = pop.right;
}
}
中序
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 代表当前节点
while (curr != null || !stack.isEmpty()) {
if(curr != null) {
//System.out.println(curr.val);
stack.push(curr); // 压入栈，为了记住回来的路
curr = curr.left;
} else {
TreeNode pop = stack.pop();
System.out.println(pop.val);
curr = pop.right;
}
}
后序
else循环就要处理右子树的逻辑
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode peek = stack.peek();
// 右子树
if (peek.right == null || peek.right == pop) {
pop = stack.pop();
System.out.println(peek.val);
}
// 待处理右子树
else {
curr = peek.right;
}
}
}
前中后
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
// 待处理左子树
System.out.println("前:" + curr.val);
curr = curr.left;
} else {
TreeNode peek = stack.peek();
// 没有右子树
if (peek.right == null) {
System.out.println("中:" + peek.val);
pop = stack.pop();
System.out.println("后:" + pop.val);
}
// 右子树处理完成
else if (peek.right == pop) {
pop = stack.pop();
System.out.println("后:" + pop.val);
}
// 待处理右子树
else {
System.out.println("中:" + peek.val);
curr = peek.right;
}
}
}
参考
