手机网站优化 工具_佛山网站优化_网络策划营销_如何做谷歌优化

一、二叉树节点定义

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}

二、递归方式

1.前序遍历

前序遍历（根-左-右）

public void preorderRecursive(TreeNode root) {if (root == null) {return;}// 访问根节点System.out.print(root.val + " ");// 递归遍历左子树preorderRecursive(root.left);// 递归遍历右子树preorderRecursive(root.right);
}

2.中序遍历

中序遍历（左-根-右）

public void inorderRecursive(TreeNode root) {if (root == null) {return;}// 递归遍历左子树inorderRecursive(root.left);// 访问根节点System.out.print(root.val + " ");// 递归遍历右子树inorderRecursive(root.right);
}

3.后序遍历

后序遍历（左-右-根）

public void postorderRecursive(TreeNode root) {if (root == null) {return;}// 递归遍历左子树postorderRecursive(root.left);// 递归遍历右子树postorderRecursive(root.right);// 访问根节点System.out.print(root.val + " ");
}

三、非递归方式

1.前序遍历

前序遍历（根-左-右）

public void preorderIterative(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.val + " ");// 先压入右节点，再压入左节点，保证左节点先出栈if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}
}

2.中序遍历

中序遍历（左-根-右）

public void inorderIterative(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode curr = root;while (curr != null || !stack.isEmpty()) {// 一直向左走，把所有左节点压栈while (curr != null) {stack.push(curr);curr = curr.left;}curr = stack.pop();System.out.print(curr.val + " ");// 转向右子树curr = curr.right;}
}

3.后序遍历

后序遍历（左-右-根）

public void postorderIterative(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();// 用于反转顺序Stack<Integer> output = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();output.push(node.val);// 注意这里先左后右，这样输出栈的顺序就是右-左-根// 反转后就是左-右-根if (node.left != null) {stack.push(node.left);}if (node.right != null) {stack.push(node.right);}}// 输出结果while (!output.isEmpty()) {System.out.print(output.pop() + " ");}
}

4.层级遍历

层级遍历（Level Order Traversal）也称为广度优先遍历（BFS），是按层次从上到下、从左到右访问二叉树节点的遍历方式。

public void levelOrderTraversal(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}
}

5.分层打印

分层打印的实现（按层次输出）

public void levelOrderWithLevels(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int levelCount = 0;while (!queue.isEmpty()) {int levelSize = queue.size();System.out.print("Level " + (levelCount++) + ": ");for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}System.out.println();}
}

四、测试用例

public static void main(String[] args) {// 构建二叉树//       1//      / \//     2   3//    / \//   4   5TreeNode 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);BinaryTreeTraversal traversal = new BinaryTreeTraversal();System.out.println("递归前序遍历:");traversal.preorderRecursive(root);System.out.println("\n非递归前序遍历:");traversal.preorderIterative(root);System.out.println("\n\n递归中序遍历:");traversal.inorderRecursive(root);System.out.println("\n非递归中序遍历:");traversal.inorderIterative(root);System.out.println("\n\n递归后序遍历:");traversal.postorderRecursive(root);System.out.println("\n非递归后序遍历:");traversal.postorderIterative(root);System.out.println("\n基本层级遍历:");traversal.levelOrderTraversal(root);System.out.println("\n\n分层打印层级遍历:");traversal.levelOrderWithLevels(root);
}

打印结果