二叉树的先序遍历、中序遍历、后序遍历、层次遍历的迭代实现以及递归实现

同时发布：https://notes.daiyuhe.com/traversal-of-binary-tree/

遍历二叉树的迭代实现

先序遍历：根-左-右

实现思路：使用栈。由于栈是后进先出，所以push的顺序为右-左。

1. 首先入栈root
2. node = 出栈，记录当前值
3. 入栈node.right
4. 入栈node.left
5. 重复2-4，直到栈空

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) {
        return list;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        list.add(node.val);

        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }

    return list;
}

中序遍历：左-根-右

实现思路：使用栈。当前节点有左节点时，入栈左节点。当前节点没有左节点时，记录当前值，然后入栈右节点。

1. if root.left != null 转2 else 转4
2. 入栈root.left
3. root = root.left 转1
4. node = 出栈，记录当前值
5. 入栈node.right
6. root = node.right
7. 重复1-6，直到栈空以及root为null

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) {
        return list;
    }

    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        }else {
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }
    }

    return list;
}

后序遍历：左-右-根

实现思路：使用栈。我们通过根-右-左的方式将每次获取的值保存到列表的第一位，最后得到的结果就会是左-右-根。

1. 首先入栈root
2. node = 出栈，记录当前值到列表第一位
3. 入栈node.left
4. 入栈node.right
5. 重复2-4，直到栈空
   我们出栈的顺序是根-右-左，由于每次记录到位置0，这样就将顺序反向形成左-右-根。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) {
        return list;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        list.add(node.val);

        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }

    return list;
}

层次遍历

实现思路：使用队列。由于栈的特性使用栈很难搞定层次遍历，我们借用队列的先进先出特性实现二叉树的层次遍历。

1. 入队root
2. node = 出队，记录当前值
3. 入队node.left
4. 入队node.right
5. 重复2-4，直到队列为空

public List<Integer> levelOrderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) {
        return list;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        list.add(node.val);

        if (node.left != null) {
            queue.add(node);
        }
        if (node.right != null) {
            queue.add(node);
        }
    }
    return list;
}

遍历二叉树的递归实现

先序遍历

public void preorderRecursion(List<Integer> list, TreeNode root) {
    if (root == null) {
        return;
    }

    list.add(root.val);
    preorderRecursion(list, root.left);
    preorderRecursion(list, root.right);
}

中序遍历

public void inorderRecursion(List<Integer> list, TreeNode root) {
    if (root == null) {
        return;
    }

    inorderRecursion(list, root.left);
    list.add(root.val);
    inorderRecursion(list, root.right);
}

后序遍历

public void postorderRecursion(List<Integer> list, TreeNode root) {
    if (root == null) {
        return;
    }

    postorderRecursion(list, root.left);
    postorderRecursion(list, root.right);
    list.add(root.val);
}