二叉树的前序遍历、中序遍历、后序遍历、层序遍历
1.节点定义
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
2.中序遍历
左-根-右
public static void printTreeInOrder(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
printTreeInOrder(root.left);
}
System.out.print(root.val + "\t");
if (root.right != null) {
printTreeInOrder(root.right);
}
}
3.先序遍历
根-左-右
public static void printTreePreOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + "\t");
if (root.left != null) {
printTreePreOrder(root.left);
}
if (root.right != null) {
printTreePreOrder(root.right);
}
}
4.后序遍历
左-右-根
public static void printTreePostOrder(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
printTreePostOrder(root.left);
}
if (root.right != null) {
printTreePostOrder(root.right);
}
System.out.print(root.val + "\t");
}
5.层序遍历
利用队列
public static void printTreeLevelOrder(TreeNode root) {
LinkedList queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.val + "\t");
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
}
System.out.println();
}