剑指offer第59题:按之字形顺序打印二叉树——双栈与单队列四种解法剖析(InterviewGuide 刷题笔记)

原创2026-10-12 10:27:401,636 阅读
文章标签:教程

剑指offer第59题:按之字形顺序打印二叉树——双栈与单队列四种解法剖析(InterviewGuide 刷题笔记)

本篇讲解《剑指Offer》第59题「按之字形顺序打印二叉树」:第一行从左到右打印、第二行从右到左打印、第三行再从左到右打印,以此类推。本文基于 InterviewGuide 仓库中阿秀的 刷题笔记原文 展开,完整继承其中 3 种一刷解法与 2 种二刷优化版本,并结合仓库内同源题目(第60题、力扣面试题32-III)做纵深对比。读完本文,你将掌握:用两个栈交替实现「之字形」遍历的原理与入栈顺序细节、用单个队列加奇偶层翻转的简洁写法,以及 std::move 与 vector<int>().swap(temp) 两种容器清理手法在刷题中的实际意义。

一、题目理解:从普通层序遍历到之字形

1.1 题目描述

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

本题目出自牛客网剑指offer专题题库(No59),同时对应力扣「面试题 32 - III. 从上到下打印二叉树 III」,两者是同一道题的不同平台形态,仓库中均有对应笔记。

1.2 示例与输出对照

输入:

{8,6,10,5,7,9,11}

这表示一棵按层序序列化描述的二叉树,树形结构为:

        8
       / \
      6   10
     / \  / \
    5   7 9  11

返回值:

[[8],[10,6],[5,7,9,11]]

对照来看:

  • 第 1 层只有根节点 8,从左到右输出 [8];
  • 第 2 层从左到右本来是 6,10,之字形要求从右到左,故输出 [10,6];
  • 第 3 层从左到右本来是 5,7,9,11,之字形要求恢复从左到右,故输出 [5,7,9,11]。

对比仓库内 第60题「把二叉树打印成多行」:同样的输入 {8,6,10,5,7,9,11},普通层序遍历的返回值是 [[8],[6,10],[5,7,9,11]]。可以看出,第60题是「每层同向」,第59题是「逐层反向」,两道题互为变体,是面试中典型的对比提问组合。

1.3 核心难点在哪里

普通层序遍历用队列天然满足「先进先出」的逐层顺序;但之字形要求偶数层整体反序。解题突破口有两个方向:

  1. 借助栈的 LIFO 特性:用两个栈分别负责「偶数层」与「奇数层」的节点暂存,交替弹出即可自然实现方向翻转——这是剑指offer官方推荐思路,也是本笔记第一、第二种解法的基础;
  2. 照常层序遍历,输出时按层翻转:仍然用队列完成层序遍历,奇数层直接输出、偶数层把该层结果反转后再输出——这是本笔记第三种解法的思路,代码最简洁。

两种方向的时间复杂度都是 O(n)(n 为节点总数),区别主要在空间与常数因子。

二、解法一:双栈法——注意左右子树在两个栈中的入栈顺序

这是原笔记给出的第一种解法,也是本题的经典解法。核心思想是使用两个栈 left_right_st 与 right_left_st 交替处理相邻两层:left_right_st 负责「从左到右」输出的那一层,right_left_st 负责「从右到左」输出的那一层。

vector<vector<int> > Print(TreeNode* pRoot) {
	vector<vector<int>> result;
	if (pRoot == nullptr) return result;
	stack<TreeNode*> left_right_st;
	stack<TreeNode*> right_left_st;
	left_right_st.push(pRoot);
	while (left_right_st.size() ||  right_left_st.size()) {
		if (!left_right_st.empty()) {
			vector<int> temp;
			TreeNode* node;
			while (!left_right_st.empty()) {
				node = left_right_st.top();
				temp.push_back(node->val);
				if (node->left)//这里先左再右
					right_left_st.push(node->left);
				if (node->right)
					right_left_st.push(node->right);
				left_right_st.pop();
			}
			result.push_back(temp);
		}

		if (!right_left_st.empty()) {
			vector<int> temp;
			TreeNode* node;
			while (!right_left_st.empty()) {
				node = right_left_st.top();
				temp.push_back(node->val);
				if (node->right)//这里需要是先右再左
					left_right_st.push(node->right);
				if (node->left)
					left_right_st.push(node->left);
				right_left_st.pop();
			}
			result.push_back(temp);
		}

	}
	return result;
}

2.1 运行流程拆解

以示例树为例逐步推演:

  1. 根节点 8 入 left_right_st;
  2. 处理 left_right_st:弹出 8,temp = [8];按「先左再右」把 6、10 依次压入 right_left_st(栈顶是 10);result = [[8]];
  3. 处理 right_left_st:先弹栈顶 10(得到从右到左的顺序),再把 10 的右子 9、左子 7 依次压入 left_right_st;随后弹出 6,把 6 的右子 7、左子 5 压入 left_right_st,此时 left_right_st 从栈顶到栈底为 7,5,7,9……由于 7 被重复压入两次(既是 6 的右子又是 10 的左子,即节点 7 仅存在于题目序列中的 5,7,9,11 位置),temp = [10,6],result = [[8],[10,6]];
  4. 处理 left_right_st:按先左后右压入下一层,输出 [5,7,9,11]。

2.2 关键点:入栈顺序为何一正一反

这是本题最容易写错、也最值得向面试官展开说明的细节:

  • 当弹出 left_right_st 的节点(这一层从左到右输出)时,为了下一层 right_left_st 弹出时呈「从右到左」,必须把子节点按「先左再右」压栈。因为栈后进先出,后压入的右子节点会先被弹出,正好实现右到左;
  • 反之,当弹出 right_left_st 的节点(这一层从右到左输出)时,为了让下一层 left_right_st 恢复「从左到右」,必须把子节点按「先右再左」压栈,后压入的左子节点先弹出,正好实现左到右。

原笔记在这两处分别用注释标注了 //这里先左再右 与 //这里需要是先右再左,正是为了让读者牢记这个对偶关系。压栈方向反了,输出的层序就会错乱。

三、解法二:对双栈法的代码优化

解法一虽然正确,但把 vector<int> temp 声明在了两个独立的 if 分支内,结构略显冗余。解法二将其提取到循环体顶部,并通过 vector<int>().swap(temp) 在两层之间清空复用同一个容器:

vector<vector<int> > Print(TreeNode* pRoot) {
	vector<vector<int>> result;
	if (pRoot == nullptr) return result;
	stack<TreeNode*> left_right_st;
	stack<TreeNode*> right_left_st;
	left_right_st.push(pRoot);
	while (left_right_st.size() ||  right_left_st.size()) {
		vector<int> temp;
		TreeNode* node;
		if (!left_right_st.empty()) {
			while (!left_right_st.empty()) {
				node = left_right_st.top();
				temp.push_back(node->val);
				if (node->left)
					right_left_st.push(node->left);
				if (node->right)
					right_left_st.push(node->right);
				left_right_st.pop();
			}
			result.push_back(temp);

		}
		vector<int>().swap(temp);
		if (!right_left_st.empty()) {
			while (!right_left_st.empty()) {
				node = right_left_st.top();
				temp.push_back(node->val);
				if (node->right)
					left_right_st.push(node->right);
				if (node->left)
					left_right_st.push(node->left);
				right_left_st.pop();
			}
			result.push_back(temp);
		}

	}
	return result;
}

3.1 关于 vector<int>().swap(temp)

vector<int>().swap(temp) 的本质是:构造一个空的临时 vector,与 temp 交换内部缓冲区,从而把 temp 的容量与元素一并释放,等价于 temp.clear() 加容量收缩。在牛客网这类内存统计严格的环境中,它能避免 temp 在两层复用之间残留上一层的容量,从而降低峰值内存占用;代价是交换后临时对象析构时释放缓冲区,后续再向 temp 写入会重新分配。

提示:如果你更在意运行效率而非内存占用,也可以只用 temp.clear()(保留容量、避免反复分配)。两种写法都正确,刷题时按平台的内存统计口径取舍即可。

四、解法三:只用一个队列,很不错的想法

如果说双栈法是「面向方向设计的数据结构」,单队列法就是「层序遍历 + 事后翻转」的简化思维:层序遍历的队列写法与第60题几乎一模一样,只在最后按奇偶层决定是否反转结果:

vector<vector<int> > Print(TreeNode* pRoot) {
	vector<vector<int>> result;
	if (pRoot == nullptr) {
		return result;
	}
	queue<TreeNode*> q;
	q.push(pRoot);
	bool isLeft = false;
	while (!q.empty()) {
		int rowLen = q.size();
		vector<int> temp;
		while(rowLen--) {
			TreeNode* curNode = q.front();
			q.pop();
			if (curNode != nullptr) {
				temp.push_back(curNode->val);
				if (curNode->left)q.push(curNode->left);
				if (curNode->right)q.push(curNode->right);
			}
		}
		isLeft = !isLeft;
		if (!isLeft) {
			result.push_back(vector<int>(temp.rbegin(), temp.rend()));//注意这里是翻转一下的
		}
		else {
			result.push_back(temp);
		}
	}
	return result;
}

4.1 关键逻辑解读

  • int rowLen = q.size(); 先记下当前层的节点数,内层 while(rowLen--) 恰好弹出这一层的全部节点,这是层序遍历「按层切分」的通用手法,与 第60题解法 的 int len = q.size() 思路一致;
  • isLeft 初始为 false,每次处理完一层取反。!isLeft 为真时表示当前是偶数层(从右到左),此时用 vector<int>(temp.rbegin(), temp.rend()) 构造一个逆序副本再压入结果;否则直接压入;
  • 原笔记特别用注释强调 //注意这里是翻转一下的,提醒读者不要漏掉偶数层的逆序处理。

4.2 三种解法对比小结

解法 数据结构 空间复杂度 特点
解法一 双栈 两个 stack O(n)(最坏两层各存约 n/2) 教科书经典思路,入栈顺序需牢记
解法二 双栈优化 两个 stack O(n) 与解法一相同,结构更紧凑、内存可控
解法三 单队列 一个 queue O(n) 代码最简洁,与层序遍历代码高度复用

三者时间复杂度均为 O(n)(每个节点恰好访问一次),实际运行差异主要体现在常数因子与内存分配策略上,没有绝对优劣。

五、二刷解法再剖析:双栈 + std::move 的标准形态

原笔记在「二刷」阶段记录了作者重做该题时的两份代码,相比一刷版本更注重两点:空结果保护 与 move 语义避免拷贝。

5.1 二刷版本一:带空值保护的直白写法

运行时间:4ms  占用内存:360k
vector<vector<int> > Print(TreeNode* pRoot) {
    if(pRoot == nullptr) return vector<vector<int>>();
    vector<vector<int>> result;
    stack<TreeNode*> left_right,right_left;
    left_right.push(pRoot);
    TreeNode*node = nullptr;
    vector<int> temp;
    while(!left_right.empty() || !right_left.empty()){
        vector<int>().swap(temp);
        while(!left_right.empty()){
            node = left_right.top();
            temp.push_back(node->val);
            left_right.pop();
            if(node->left) right_left.push(node->left);
            if(node->right) right_left.push(node->right);
        }
        if(temp.size() > 0)    result.push_back(std::move(temp));

        vector<int>().swap(temp);
        while(!right_left.empty()){
            node = right_left.top();
            temp.push_back(node->val);
            right_left.pop();
            if(node->right) left_right.push(node->right);
            if(node->left) left_right.push(node->left);

        }
        if(temp.size() > 0)   result.push_back(std::move(temp));// 可能走到头了,也就是此时temp是个空,不能把空的放在结果了
    }
    return std::move(result);
}

该版本的两个亮点:

  1. if(temp.size() > 0) 判空保护:当某一层栈在轮次交替时已为空(例如遍历到最后一层后 right_left 为空),temp 保持空容器,此时不应把空数组放进 result。原笔记注释 可能走到头了,也就是此时temp是个空,不能把空的放在结果了 正是对这一边界条件的提醒;
  2. result.push_back(std::move(temp)):用移动语义把 temp 的内部缓冲区转移给结果数组,避免一次完整的元素拷贝,在节点量大的用例下能省去可观的拷贝开销。

5.2 二刷版本二:局部声明 + move 的最终形态

运行时间:3ms  占用内存:504k
vector<vector<int> > Print(TreeNode* pRoot) {
    if(pRoot == nullptr) return vector<vector<int>>();
    vector<vector<int>> result;
    stack<TreeNode*> left_right,right_left;
    left_right.push(pRoot);
    TreeNode*node = nullptr;

    while(!left_right.empty() || !right_left.empty()){
        if(!left_right.empty()){
            vector<int> temp;
            while(!left_right.empty()){
                node = left_right.top();
                temp.push_back(node->val);
                left_right.pop();
                if(node->left) right_left.push(node->left);
                if(node->right) right_left.push(node->right);
            }
            result.push_back(std::move(temp));
        }

        if(!right_left.empty()){
            vector<int> temp;
            while(!right_left.empty()){
                node = right_left.top();
                temp.push_back(node->val);
                right_left.pop();
                if(node->right) left_right.push(node->right);
                if(node->left) left_right.push(node->left);

            }
            result.push_back(std::move(temp));
        }
    }
    return std::move(result);
}

该版本回归「每个分支各自声明 temp」的结构,但统一改用 std::move 转移而非显式清理,代码语义更清晰:temp 的生命周期限定在各自分支内,天然不会残留脏数据,同时避免了 vector<int>().swap() 的重复分配。原笔记实测数据(4ms/360k 与 3ms/504k)为牛客网 C++ 环境下的单次运行记录,仅作参考,不同环境与数据规模下表现会有差异。

六、复杂度与边界条件总结

6.1 时空复杂度

  • 时间复杂度:O(n)。每个节点至多被压栈/出栈或入队/出队各一次,遍历总代价与节点数线性相关;
  • 空间复杂度:O(n)。双栈方案下,任意时刻两个栈合计保存的节点数不超过当前相邻两层节点之和(最坏 O(n));单队列方案同理,队列最多同时容纳一整层节点。

6.2 需要特别注意的边界

  1. 空树:pRoot == nullptr 时直接返回空结果(所有解法均处理);
  2. 只有单边子树:栈/队列中可能出现空指针,入栈前需 if(node->left)、if(node->right) 判空(所有解法均已处理);
  3. 末层后某一栈为空:双栈交替时,处理完最后一层后另一栈可能为空,需防止把空 temp 塞入结果(二刷版本一专门处理);
  4. 入栈顺序:从左到右层先压左再压右,从右到左层先压右再压左,写反会导致整层顺序错误。

七、与仓库内同源题目的关联

本专题笔记位于 InterviewGuide 的剑指offer刷题合集(共67题,题目顺序与牛客网剑指offer专题一致),围绕「之字形打印」这一知识点,仓库中还沉淀了两道可直接对照学习的同源题目:

此外,完整题目集合可参阅 剑指offer全集,其中第59题内容与本文档一致,方便整体按序复习。

八、小结:一道题吃透三类考点

「按之字形顺序打印二叉树」是二叉树章节中区分度很高的一道题,它同时考察了三个能力点:

  1. 层序遍历的按层切分:无论是 queue 的 rowLen = q.size() 还是双栈交替,本质都是把节点按层分组;
  2. 栈 LIFO 特性的灵活运用:一个栈解决不了方向翻转,两个栈一正一反就能让「之字形」水到渠成,入栈顺序是对偶的;
  3. 代码层面的容器管理:vector<int>().swap(temp) 清空回收、std::move 转移所有权,是刷题代码从「能跑」到「高效清晰」的分水岭。

建议按照「解法三(单队列,理解层序遍历)→ 解法一(双栈,理解方向翻转)→ 二刷版本二(双栈 + move,提升代码质量)」的顺序消化本题,再配合第60题与力扣32-III完成一轮闭环练习。

登录后查看全文
InterviewGuide