91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

java二叉樹蛇形遍歷怎么實現

小億
97
2023-12-14 17:50:32
欄目: 編程語言

蛇形遍歷二叉樹可以通過層次遍歷來實現。具體步驟如下:

  1. 首先,創建一個隊列,并將二叉樹的根節點入隊。
  2. 創建一個布爾變量leftToRight,初始值為true。該變量表示當前行的遍歷方向是從左到右還是從右到左。
  3. 開始循環,直到隊列為空。
  4. 在循環中,首先獲取當前隊列的大小,以確定當前層的節點數量。
  5. 創建一個列表levelList用來存儲當前層的節點值。
  6. 遍歷當前層的節點數量次數,每次從隊列中取出一個節點,并將其值添加到levelList中。
  7. 如果leftToRighttrue,則將節點的左右子節點依次入隊;如果leftToRightfalse,則將節點的右左子節點依次入隊。
  8. 將當前層的節點值列表levelList添加到結果列表中,然后將leftToRight取反,表示下一行的遍歷方向。
  9. 返回結果列表。

下面是Java代碼實現:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class SnakeTraversal {
    public List<List<Integer>> snakeTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> levelList = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelList.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (!leftToRight) {
                Collections.reverse(levelList);
            }
            result.add(levelList);
            leftToRight = !leftToRight;
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        SnakeTraversal snakeTraversal = new SnakeTraversal();
        List<List<Integer>> result = snakeTraversal.snakeTraversal(root);
        for (List<Integer> level : result) {
            System.out.println(level);
        }
    }
}

輸出結果:

[1]
[3, 2]
[4, 5, 6, 7]

0
蓝山县| 襄城县| 阳山县| 呼玛县| 怀化市| 汝南县| 盘锦市| 房山区| 汕头市| 斗六市| 醴陵市| 手游| 信阳市| 游戏| 确山县| 泸水县| 余姚市| 永福县| 水富县| 吉林省| 南安市| 高州市| 简阳市| 渭源县| 兴海县| 德令哈市| 浦东新区| 延寿县| 内丘县| 科尔| 绥宁县| 惠州市| 漳平市| 民权县| 肥城市| 建宁县| 中西区| 石城县| 漾濞| 昌乐县| 乌兰浩特市|