Java算法题-解析 二叉树层序遍历 II 算法问题

题目：

给定一个二叉树，返回其节点值的层序遍历。换句话说，从左到右，逐层返回二叉树的节点值。

引言

"Binary Tree Level Order Traversal II" 是一个关于二叉树的经典问题。问题的要求是按照从下到上、从左到右的顺序，返回二叉树的层序遍历结果。通常，我们使用广度优先搜索（BFS）来解决这个问题，但我们也可以使用深度优先搜索（DFS）来实现。本文将介绍如何使用深度优先搜索来解决这个问题，并提供相应的Java代码示例。

算法思路

使用深度优先搜索（DFS）来实现二叉树的层序遍历需要考虑遍历的顺序以及如何在遍历过程中组织和保存节点的值。下面是实现的基本思路：

1. 创建一个空的列表 result 用于存储每一层的节点值列表，以及一个整数 level 用于表示当前层数。
2. 开始深度优先搜索，从根节点开始。
3. 在进入每一层之前，检查 result 的大小是否等于 level。如果不等，说明需要添加一个新的层级到 result 中。
4. 将当前节点的值添加到相应层级的列表中。
5. 递归地访问左子树和右子树，同时将层级加1。
6. 最终，result 中的列表将按照从底层到顶层的顺序存储着层序遍历的结果。

代码实现

以下是使用Java实现的 "Binary Tree Level Order Traversal II" 的代码示例：

import java.util.ArrayList;
import java.util.List;

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

public class BinaryTreeLevelOrderTraversalII {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        levelOrderDFS(root, result, 0);
        reverseList(result);
        return result;
    }

    private void levelOrderDFS(TreeNode node, List<List<Integer>> result, int level) {
        if (node == null) {
            return;
        }

        if (level == result.size()) {
            result.add(0, new ArrayList<>());
        }

        result.get(result.size() - level - 1).add(node.val);

        levelOrderDFS(node.left, result, level + 1);
        levelOrderDFS(node.right, result, level + 1);
    }

    private void reverseList(List<List<Integer>> list) {
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            List<Integer> temp = list.get(left);
            list.set(left, list.get(right));
            list.set(right, temp);
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        BinaryTreeLevelOrderTraversalII solution = new BinaryTreeLevelOrderTraversalII();

        // 创建一个示例二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<List<Integer>> result = solution.levelOrderBottom(root);

        System.out.println("Binary Tree Level Order Traversal II:");
        for (List<Integer> level : result) {
            System.out.println(level);
        }
    }
}

算法分析

• 时间复杂度：由于我们需要访问二叉树的每个节点一次，所以时间复杂度是 O(n)，其中 n 是二叉树的节点数。
• 空间复杂度：递归调用栈的深度最多为二叉树的高度，所以空间复杂度是 O(h)，其中 h 是二叉树的高度。此外，存储结果的 result 列表的大小为 n，因此空间复杂度也可以表示为 O(n)。

总结

使用深度优先搜索（DFS）来实现 "Binary Tree Level Order Traversal II" 是一种巧妙的方法，它能够按照从底层到顶层的逆序返回二叉树的层序遍历结果。通过递归遍历树的同时，维护一个 result 列表，可以有效地解决这个问题。这个方法在许多情况下都可以用来处理树的层序遍历，并且可以应用于其他类似的问题。