以下是二叉树中序遍历和后序遍历的递归与非递归代码示例：
中序遍历：
递归实现：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTreeTraversalExample {
public static void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.print(root.val + " ");
inOrderTraversal(root.right);
}
public static void main(String[] args) {
// 构建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// 执行中序遍历
inOrderTraversal(root);
}
}
非递归实现（使用栈）：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTreeTraversalExample {
public static void inOrderTraversalNonRecursive(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr!= null) {
if (curr!= null) {
stack.push(curr);
curr = curr.left;
} else {
curr = stack.pop();
System.out.print(curr.val + " ");
curr = curr.right;
}
}
}
public static void main(String[] args) {
// 构建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// 执行中序遍历
inOrderTraversalNonRecursive(root);
}
}
后序遍历：
递归实现：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTreeTraversalExample {
public static void postOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root.val + " ");
}
public static void main(String[] args) {
// 构建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// 执行后序遍历
postOrderTraversal(root);
}
}
非递归实现（使用两个栈）：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTreeTraversalExample {
public static void postOrderTraversalNonRecursive(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.push(root);
while (!s1.isEmpty()) {
TreeNode curr = s1.pop();
s2.push(curr);
if (curr.left!= null) {
s1.push(curr.left);
}
if (curr.right!= null) {
s1.push(curr.right);
}
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().val + " ");
}
}
public static void main(String[] args) {
// 构建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// 执行后序遍历
postOrderTraversalNonRecursive(root);
}
}
