怎么自己做网站的优化/爱站网挖掘关键词

《剑指Offer》面试题32

 

 

题目一

从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

 

思路

利用队列的先入先出，来完成二叉树按层级打印节点信息。队列中存储二叉树的节点指针，首先将根节点入队，再将根节点出队打印，同时将左右子节点指针入队。这样每次从队列取节点，打印节点，左右子节点入队，最终完成将所有节点按层打印。

 

代码

/******************************************************************************
* 函数介绍：不分行从上到下打印二叉树
* 输入参数：pTreeRoot 二叉树根节点指针
* 输出参数：无
* 返回值：true 成功 , false 传入参数无效
* 备注：无
******************************************************************************/
bool Print_level_order(BinaryTreeNode* pTreeRoot)
{if (NULL == pTreeRoot){return false;}queue<BinaryTreeNode*> nodes;	//构造一个队列nodes//1.将根节点地址入队nodes.push(pTreeRoot);while(!nodes.empty()){//2.取出节点指针,并打印节点信息BinaryTreeNode* pNode = nodes.front();cout << pNode->m_nValue << ",";//3.节点指针出队nodes.pop();//4.将左右子节点分别入队if(pNode->m_pLeft != NULL){nodes.push(pNode->m_pLeft);}if(pNode->m_pRight != NULL){nodes.push(pNode->m_pRight);}}return true;
}

 

 

题目二

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。
 

思路

在之前的基础上，设置两个变量，分别用于纪录下一层节点的个数和当前层待打印节点的个数

 

代码

/******************************************************************************
* 函数介绍：分行从上到下打印二叉树
* 输入参数：pTreeRoot 二叉树根节点指针
* 输出参数：无
* 返回值：true 成功 , false 传入参数无效
* 备注：无
******************************************************************************/
bool Print_level_order(BinaryTreeNode* pTreeRoot)
{if (NULL == pTreeRoot){return false;}queue<BinaryTreeNode*> nodes;	//构造一个队列nodesint next_level = 0;				//下一层的节点个数int level_num = 1;				//当前层待打印的节点数//1.将根节点地址入队nodes.push(pTreeRoot);while(!nodes.empty()){//2.取出节点指针,并打印节点信息BinaryTreeNode* pNode = nodes.front();cout << pNode->m_nValue << " ";//3.节点指针出队nodes.pop();--level_num;//4.将左右子节点分别入队,并统计下一层节点数next_levelif(pNode->m_pLeft != NULL){++next_level;nodes.push(pNode->m_pLeft);}if(pNode->m_pRight != NULL){++next_level;nodes.push(pNode->m_pRight);}//5.打印分行if (level_num == 0){cout << endl;level_num = next_level;next_level = 0;}}return true;
}

 

 

题目三

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

 

分析

使用两个栈stack1、stack2来完成，先将根节点push到stack1，然后弹出打印。将根节点的左子节点和右子节点分别push到stack1，从stack1中弹出元素打印；同时将下一层的右子节点和左子节点分别push压入栈stack2中（当第二层节点从stack1中pop完，此时第三层的节点也压入stack2完成）。。直到stack1、stack2栈空，完成打印。

 

代码

/******************************************************************************
* 函数介绍：之字形打印二叉树
* 输入参数：pTreeRoot 二叉树根节点指针
* 输出参数：无
* 返回值：true 成功 , false 传入参数无效
* 备注：无
******************************************************************************/
bool Print_level_order(BinaryTreeNode* pTreeRoot)
{if (NULL == pTreeRoot){return false;}stack<BinaryTreeNode*> levels[2];	//构造一个队列nodesint current = 0;		int next = 1;			//1.将根节点地址入队levels[current].push(pTreeRoot);while (!levels[0].empty() || !levels[1].empty()){//2.从栈中弹出元素并打印BinaryTreeNode* pNode = levels[current].top();levels[current].pop();cout << pNode->m_nValue << " ";if (current == 0){if (pNode->m_pLeft != NULL)levels[next].push(pNode->m_pLeft);if (pNode->m_pRight != NULL)levels[next].push(pNode->m_pRight);}else{if (pNode->m_pRight != NULL)levels[next].push(pNode->m_pRight);if (pNode->m_pLeft != NULL)levels[next].push(pNode->m_pLeft);}if (levels[current].empty()){cout << endl;current = 1 - current;next = 1 - next;}}return true;
}

 

 

源码链接：https://gitee.com/hinzer/sword_to_offer/tree/master/questions