四种遍历二叉树

2021/5/23 algorithm

节点类

Public Class Node {
    public String data;
    public Node left;
    public Node right;
}

# 层序遍历二叉树

public static void levelOrder(Node node) {
    if (node == null) return;
    List<String> res = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.offer(node);
    while (!queue.isEmpty()) {
        Node curNode = queue.poll();
        res.add(curNode.data);
        if (curNode.left != null) queue.offer(curNode.left);
        if (curNode.right != null) queue.offer(curNode.right);
    }
    System.out.println(res);
}

# 前序遍历二叉树

递归

public static void preOrderTraveral(Node node) {
    if (node == null) return;
    System.out.print(node.data);
    preOrderTraveral(node.left);
    preOrderTraveral(node.right);
}

非递归

public static void preOrderTraveral(Node node) {
    if (node == null) return;
    List<String> res = new ArrayList<>();
    Stack<Node> stack = new Stack<>();
    stack.push(node);
    while (!stack.isEmpty()) {
        Node curNode = stack.pop();
        res.add(curNode.data);
        if (curNode.right != null) stack.push(curNode.right);
        if (curNode.left != null) stack.push(curNode.left);
    }
    System.out.println(res);
}

# 中序遍历二叉树

递归

public static void inOrderTraveral(Node node) {
    if (node == null) return;
    inOrderTraveral(node.left);
    System.out.print(node.data);
    inOrderTraveral(node.right);
}

非递归

public static void inOrderTraveral(Node node) {
    if (node == null) return;
    List<String> res = new ArrayList<>();
    Stack<Node> stack = new Stack<>();
    TreeNode curNode = node;
    while (curNode != null || !stack.isEmpty()) {
        while (curNode != null) {
            stack.push(curNode);
            curNode = curNode.left;
        }
        Node popNode = stack.pop();
        res.add(popNode.data);
        curNode = popNode.right;
    }
    System.out.println(res);
}

# 后序遍历二叉树

递归

public static void postOrderTraveral(Node node) {
    if (node == null) return;
    postOrderTraveral(node.left);
    postOrderTraveral(node.right);
    System.out.print(node.data);
}

非递归

public static void postOrderTraveral(Node node) {
    if (node == null) return;
    List<String> res = new ArrayList<>();
    Stack<Node> stack = new Stack<>();
    stack.push(node);
    while (!stack.isEmpty()) {
        Node curNode = stack.pop();
        res.add(curNode.data);
        if (curNode.left != null) stack.push(curNode.left);
        if (curNode.right != null) stack.push(curNode.right);
    }
    Collections.reverse(res);
    System.out.println(res);
}