103.二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 树中节点数目在范围 [0, 2000] 内
• $-100\le Node.val\le 100$

解法一(层序遍历+reverse)

思路分析

1. 参照题二叉树的层序,最简单的思路是,根据层序遍历结果,对需要从右往左遍历的那层二叉树节点进行反转即可;

实现代码

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean flag = true;    // 标记遍历顺序 起始：从左往右
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; ++ i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            ans.add(level);
        }
        // 按照锯齿规律进行反转
        int size = ans.size();
        for (int i = 0; i < size; ++ i) {
            if (i % 2 == 1) {
                Collections.reverse(ans.get(i));
            }
        }
        return ans;
    }
}

运行结果

2024/10/08 16:16:56

解答成功:

执行耗时:1 ms,击败了78.76% 的Java用户

内存消耗:41.11 MB,击败了87.52% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

解法二(层序遍历)

思路分析

1. 即在遍历的过程中,按照从左到右或从右往左的顺序对二叉树节点进行层序遍历;
2. 可以使用List列表的LinkedList双向列表, 对于从左往右遍历的节点, 则节点添加到末尾即可; 对于从右往左遍历的节点, 则每次将节点添加从首添加即可;

实现代码

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> ans = new ArrayList<>();
		if (root == null) {
			return ans;
		}
		Queue<TreeNode> queue = new ArrayDeque<>();
		queue.offer(root);
		// 标记遍历顺序 初始：从左往右
		boolean isFromLeft = true;
		while (!queue.isEmpty()) {
			int size = queue.size();
			LinkedList<Integer> level = new LinkedList<>();
			for (int i = 0; i < size; ++ i) {
				TreeNode node = queue.poll();
				if (isFromLeft) {
					level.addLast(node.val);
				} else {
					level.addFirst(node.val);
				}
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			isFromLeft = !isFromLeft;
			ans.add(level);
		}
		return ans;
    }
}

运行结果

2024/10/08 16:38:23

解答成功:

执行耗时:1 ms,击败了78.76% 的Java用户

内存消耗:41.2 MB,击败了58.51% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$