기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

트리의 계층적 순회는 트리의 모든 노드를 계층적 순서대로 방문하는 순회 방법을 의미합니다. 구체적인 단계는 다음과 같습니다.

1. 루트 노드부터 시작하여 루트 노드를 대기열에 넣습니다.
2. 대기열이 빌 때까지 반복합니다.
   • 대기열에서 노드를 팝하고 액세스합니다.
   • 이 노드의 모든 하위 노드를 순서대로 대기열에 추가합니다.
3. 완전한 순회.

레벨 순회에 대한 관련 지식 포인트:

1. 대기열: 계층적 순회에서는 노드를 임시로 저장하기 위해 대기열을 사용해야 합니다. 노드에 액세스할 때마다 해당 하위 노드가 차례로 대기열에 들어가고 다음 주기에서 액세스를 위해 대기열의 헤드 노드가 제거됩니다.
2. 루프: 레벨 순회에는 큐가 빌 때까지 루프 작업이 필요합니다. 루프 동안 노드는 모든 노드가 순회될 때까지 지속적으로 추가되고 대기열에서 제거됩니다.
3. 노드 액세스: 노드에 대한 액세스는 필요에 따라 결정될 수 있으며, 노드의 값을 인쇄하거나 다른 작업을 수행할 수 있습니다.
4. 하위 노드 대기열에 넣기: 계층적 순회에서는 후속 루프에서 계속 액세스하려면 각 노드의 모든 하위 노드를 대기열에 넣어야 합니다.

아이디어:

1. 먼저 대기열을 만들고 루트 노드를 대기열에 넣습니다.
2. 대기열이 빌 때까지 반복합니다.
   • 대기열에서 노드를 팝하고 액세스합니다.
   • 이 노드의 모든 하위 노드를 순서대로 대기열에 추가합니다.
3. 완전한 순회.

이 아이디어는 큐를 사용하여 계층적 순회를 구현하는 핵심입니다. 노드가 대기열에서 제거되고 액세스될 때마다 해당 하위 노드가 대기열에 추가되므로 계층적 순서에 따른 액세스가 보장됩니다.

예:

102. 이진 트리의 레벨 순서 순회

이진 트리의 루트 노드를 제공합니다.root, 노드 값을 반환합니다.레벨순회 . (즉, 왼쪽에서 오른쪽으로 레이어별로 모든 노드를 방문합니다.)

예시 1:

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

예 2:

输入：root = [1]
输出：[[1]]

예시 3:

输入：root = []
输出：[]

// 层序遍历二叉树并返回结果列表
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> lists = new ArrayList<>(); // 用于存储层序遍历结果的列表
    Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列，用于层序遍历
    if (root == null) {
        return new ArrayList<List<Integer>>(); // 如果根节点为空，直接返回空列表
    }
    queue.add(root); // 将根节点加入队列
    while (!queue.isEmpty()) {
        int size = queue.size(); // 当前层的节点数
        List<Integer> list = new ArrayList<>(); // 用于存储当前层节点值的列表
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll(); // 出队列
            list.add(node.val); // 将节点值加入当前层列表
            // 将当前节点的左右子节点加入队列，以便遍历下一层
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        lists.add(list); // 将当前层的节点值列表加入最终结果列表
    }
    return lists; // 返回层序遍历结果列表
}