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

题目描述

输入二叉树的根节点 root。按层输出节点值，但每层的读取方向轮流变化。

最上面一层（根所在层）从左往右，下一层改为从右往左，再下一层又回到从左往右，依此交替。

返回一个列表，第 k 个元素是第 k 层按上述方向得到的节点值序列。树为空时返回 []。树用层序数组表示，null 代表空位。

示例 1

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

解释：第二层反向读取，所以是 [20,9]；第三层又恢复从左往右。

示例 2

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

解释：只有一层。

示例 3

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

解释：空树返回空列表。

数据范围

节点总数在 [0, 2000] 之间。
-100 <= Node.val <= 100

解题思路：广度优先搜索 + 反转

锯齿形只改变每层的输出顺序，不改变“按层访问”这件事。所以照常做 BFS：每层先记下队列长度，弹出这么多节点组成一层。用布尔变量 left 记录方向，方向向右时把本层反转后再放进结果，每层结束翻转一次 left。

为什么正确

每次进入 while 循环时，队列里恰好是下一层的全部节点，并按从左到右的顺序排列。

复杂度分析

时间 O(n)，每个节点入队出队各一次；空间 O(n)，队列最多存一层节点。

易错点

不要试图在入队时就按反方向放子节点，那样下一层的队列顺序会被打乱。队列始终按从左到右，只在输出时反转。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        res, q, left = [], collections.deque([root]), True
        while q:
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(level if left else level[::-1])
            left = not left
        return res

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        boolean left = true;
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int k = q.size(); k > 0; k--) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            if (!left) {
                Collections.reverse(level);
            }
            res.add(level);
            left = !left;
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) {
            return {};
        }
        vector<vector<int>> res;
        deque<TreeNode*> q{root};
        bool left = true;
        while (!q.empty()) {
            vector<int> level;
            for (int k = q.size(); k > 0; k--) {
                TreeNode* node = q.front();
                q.pop_front();
                level.push_back(node->val);
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            if (!left) {
                reverse(level.begin(), level.end());
            }
            res.push_back(level);
            left = !left;
        }
        return res;
    }
};

func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	res, q, left := [][]int{}, []*TreeNode{root}, true
	for len(q) > 0 {
		level := []int{}
		for k := len(q); k > 0; k-- {
			node := q[0]
			q = q[1:]
			level = append(level, node.Val)
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		if !left {
			for i, j := 0, len(level)-1; i < j; i, j = i+1, j-1 {
				level[i], level[j] = level[j], level[i]
			}
		}
		res = append(res, level)
		left = !left
	}
	return res
}

var zigzagLevelOrder = function(root) {
    if (!root) {
        return [];
    }
    const res = [], q = [root];
    let left = true;
    while (q.length) {
        const level = [];
        for (let k = q.length; k > 0; k--) {
            const node = q.shift();
            level.push(node.val);
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
        res.push(left ? level : level.reverse());
        left = !left;
    }
    return res;
};

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    if (!root) {
        return [];
    }
    const res: number[][] = [], q: TreeNode[] = [root];
    let left = true;
    while (q.length) {
        const level: number[] = [];
        for (let k = q.length; k > 0; k--) {
            const node = q.shift()!;
            level.push(node.val);
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
        res.push(left ? level : level.reverse());
        left = !left;
    }
    return res;
}

载入编辑器，自己跑一遍 →

其他解法

两种方法都是先得到每层从左到右的顺序，再反转奇数层；区别只在按层收集节点的方式是队列还是递归。

解法 2：深度优先搜索时间 O(n)，空间 O(h)

先按先左后右的顺序递归，带上深度 depth，把节点值追加到第 depth 层，得到普通层序结果。偶数层保持不变，奇数层在最后反转一次。

辅助空间取决于树高 h，不需要队列。深链树递归很深，Python 需要调高递归深度。

import sys

class Solution:
    def zigzagLevelOrder(self, root):
        sys.setrecursionlimit(10000)
        res = []
        def dfs(node, depth):
            if not node:
                return
            if depth == len(res):
                res.append([])
            res[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        dfs(root, 0)
        for i in range(1, len(res), 2):
            res[i].reverse()
        return res

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, 0, res);
        for (int i = 1; i < res.size(); i += 2) {
            Collections.reverse(res.get(i));
        }
        return res;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> res) {
        if (node == null) return;
        if (depth == res.size()) res.add(new ArrayList<>());
        res.get(depth).add(node.val);
        dfs(node.left, depth + 1, res);
        dfs(node.right, depth + 1, res);
    }
}

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        dfs(root, 0, res);
        for (int i = 1; i < (int)res.size(); i += 2) {
            reverse(res[i].begin(), res[i].end());
        }
        return res;
    }

    void dfs(TreeNode* node, int depth, vector<vector<int>>& res) {
        if (!node) return;
        if (depth == (int)res.size()) res.push_back({});
        res[depth].push_back(node->val);
        dfs(node->left, depth + 1, res);
        dfs(node->right, depth + 1, res);
    }
};

func zigzagLevelOrder(root *TreeNode) [][]int {
	res := [][]int{}
	var dfs func(node *TreeNode, depth int)
	dfs = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}
		if depth == len(res) {
			res = append(res, []int{})
		}
		res[depth] = append(res[depth], node.Val)
		dfs(node.Left, depth+1)
		dfs(node.Right, depth+1)
	}
	dfs(root, 0)
	for i := 1; i < len(res); i += 2 {
		level := res[i]
		for a, b := 0, len(level)-1; a < b; a, b = a+1, b-1 {
			level[a], level[b] = level[b], level[a]
		}
	}
	return res
}

var zigzagLevelOrder = function(root) {
    const res = [];
    const dfs = (node, depth) => {
        if (!node) return;
        if (depth === res.length) res.push([]);
        res[depth].push(node.val);
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    };
    dfs(root, 0);
    for (let i = 1; i < res.length; i += 2) {
        res[i].reverse();
    }
    return res;
};

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    const res: number[][] = [];
    const dfs = (node: TreeNode | null, depth: number): void => {
        if (!node) return;
        if (depth === res.length) res.push([]);
        res[depth].push(node.val);
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    };
    dfs(root, 0);
    for (let i = 1; i < res.length; i += 2) {
        res[i].reverse();
    }
    return res;
}

二叉树专题的其他题目

查看二叉树全部题目 →