题目

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

代码

public static IList<IList<int>> Method(TreeNode root)
{
    IList<IList<int>> res = new List<IList<int>>();
    Stack<TreeNode> stack1 = new Stack<TreeNode>(); // 每行数据从左到右读入
    Stack<TreeNode> stack2 = new Stack<TreeNode>(); // 每行数据从右到做读入
    if (root == null)
    {
        return res;
    }

    stack2.Push(root);
    while (stack1.Count != 0 || stack2.Count != 0)
    {
        var sub = new List<int>();
        TreeNode cur;
        if (stack1.Count != 0)
        {
            while (stack1.Count != 0)
            {
                cur = stack1.Pop();
                sub.Add(cur.val);
                if (cur.right != null)
                {
                    stack2.Push(cur.right);
                }
                if (cur.left != null)
                {
                    stack2.Push(cur.left);
                }
            }
            res.Add(sub);
        }
        else
        {
            while (stack2.Count != 0)
            {
                cur = stack2.Pop();
                sub.Add(cur.val);
                if (cur.left != null)
                {
                    stack1.Push(cur.left);
                }
                if (cur.right != null)
                {
                    stack1.Push(cur.right);
                }
            }
            res.Add(sub);
        }
    }

    return res;
}

注意点

• if (root == null)，对结点空判断
• while (stack1.Count != 0 || stack2.Count != 0)，while 循环退出条件

可以换一种思路：按正常 BFS 算法进行遍历，遇到奇数层（从0层开始），将元素反转。