溫馨提示×

java二叉樹蛇形遍歷怎么實現(xiàn)

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

蛇形遍歷二叉樹可以通過層次遍歷來實現(xiàn)。具體步驟如下：

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

下面是Java代碼實現(xiàn)：

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);
        }
    }
}

輸出結(jié)果：

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

0 踩