剑指Offer（数据结构与算法面试题精讲）C++版——day14
- 题目一：二叉树广度优先搜索
- 题目二：在完全二叉树中添加节点
- 题目三：二叉树中每层的最大值
- 附录：源码gitee仓库
题目一：二叉树广度优先搜索
题目：二叉树的广度优先搜索可能听起来稍微有点陌生，其实就是二叉树的层序遍历，即从上到下按层遍历二叉树，从二叉树的根节点开始，先遍历二叉树的第1层，再遍历第2层，接着遍历第3层，并以此类推。例如，如果按照广度优先的顺序遍历图7.2中的二叉树，那么先后遍历节点8、节点6、节点10、节点5、节点7、节点9、节点11。
由于之后很多关于二叉树的算法题目，所以这里先分析一下二叉树的数据结构、构建和遍历方法。对于二叉树的数据结构，类似于双向链表，其实这个结构熟悉之后也不复杂，只是如果刚接触指针可能会觉得有点绕，把握好指针指向就行：
struct treeNode {int val;treeNode * left;treeNode * right;treeNode(int data):val(data),left(nullptr),right(nullptr) {}
};
对于二叉树的构建，可以对应于二叉树的遍历使用递归的方式构建，比如这里使用先序方法构建，常见的方式是使用#或者-1标识空节点。一般的话#对应的treeNode里面数据类型为char，-1对应的treeNode里面数据类型为int，这里其实都差不多，下面都使用整型来处理。以先序（根左右）为例，创建代码如下：
treeNode* createTree() {int val;cin>>val;if(val==-1) {return nullptr;} else {treeNode* node=new treeNode(val);node->left=createTree();node->right=createTree();return node;}
}
对于二叉树的遍历，一般也是使用递归的方式，比较好理解，并且代码量也比较少，先序、中序和后序的遍历方式都比较相似，这里给出先序遍历方式：
void preOrder(treeNode* tree) {treeNode * p=tree;if(p==nullptr) {return;} else {cout<<p->val<<" ";preOrder(p->left);preOrder(p->right);}
}
接下来，回到我们广度优先遍历的问题上。这里显然使用队列来实现比较方便，基本思路就是，先将根节点入队列，然后检测队列是否为空，如果队列不为空，那么从队列中弹出一个元素，并且遍历这个节点，如果左节点不为空，那么左节点入队列，如果右节点不为空，那么右节点加入队列，这样遍历直到队列为空就能够完成实现广度优先遍历，得到的代码如下：
void bfs(treeNode * tree) {queue<treeNode *> qu;treeNode * p;qu.push(tree);while(!qu.empty()) {p=qu.front();qu.pop();cout<<p->val<<" ";if(p->left) {qu.push(p->left);}if(p->right) {qu.push(p->right);}}
}
题目二：在完全二叉树中添加节点
题目：在完全二叉树中，除最后一层之外其他层的节点都是满的（第n层有2ⁿ⁻¹个节点）。最后一层的节点可能不满，该层所有的节点尽可能向左边靠拢。例如，图7.3中的4棵二叉树均为完全二叉树。
有一种思路，从上到下，从左到右遍历到最后一个节点，然后拿到该节点的兄弟节点，如果该层满了，那么取左下角节点并且添加左孩子节点。但这种方法存在一个问题，父节点不好拿到，并且兄弟节点可能不与当前节点在同一个父节点下。分析发现，可以站在层序遍历的角度分析。第一种情况，如果当前遍历的节点有左子节点但是没有右子节点，那么说明下次添加需要将节点插入到右子节点空缺的位置；第二种情况，如果当前遍历到的节点没有左子节点，比如图©中在加入8节点之前，那么在遍历的过程中可以发现4节点没有左子节点，这样就不需要去遍历4节点右侧的节点了，那是否存在右侧节点为空被忽略了呢？比如7节点这个位置为空。这种假设是不成立的，如果7的位置为空，那么在遍历3节点的时候出现了第一种情况了。因此这样方法可行且高效。于是得到如下代码：
treeNode * addTreeNode(treeNode* tree,int val) {queue<treeNode *> qu;treeNode *p,*newNode;if(!tree) {return new treeNode(val);} else {newNode=new treeNode(val);qu.push(tree);while(!qu.empty()) {p=qu.front();qu.pop();if(p->left) {qu.push(p->left);} else {p->left=newNode;return tree;}if(p->right) {qu.push(p->right);} else {p->right=newNode;return tree;}}}
}
题目三：二叉树中每层的最大值
题目：输入一棵二叉树，请找出二叉树中每层的最大值。例如，输入图7.4中的二叉树，返回各层节点的最大值[3, 4, 9]。
这里因为需要统计每一行的最大值，因此需要考虑使用层序遍历的方式。关键在于怎么去将每一层的遍历给拆分开，解决的方法比较巧妙，利用好qu.size()能够拿到当前队列的元素个数的特点。我们从上到下分析，第一层加入第一个节点，此时队列个数为1，分析完1节点之后，弹出，同时1节点的左右两个孩子节点入队，也就是这里的4，2节点，队列大小变为2，接下来4，2节点出队列将5，1，9节点加入队列。于是就能利用队列大小将每一层拆分，统计最大值就很方便了，最终得到如下代码：
void getMaxPreLevel(treeNode * tree,vector<int> &vec) {queue<treeNode *> qu;treeNode * p;int levelMax;if(!tree)return ;qu.push(tree);while(!qu.empty()) {levelMax=0;for(int i=0,size=qu.size(); i<size; ++i) {p=qu.front();qu.pop();levelMax=max(levelMax,p->val);if(p->left) {qu.push(p->left);}if(p->right) {qu.push(p->right);}}vec.push_back(levelMax);}
}
附录：源码gitee仓库
考虑到有些算法需要模拟数据，如果全部放进来代码显得过长，不利于聚焦在算法的核心思路上。于是把所有的代码整理到了开源仓库上，如果想要看详细模拟数据，可在开源仓库自取：【凌空暗羽/剑指offer-C++版手写代码】。
我是【Jerry说前后端】，本系列精心挑选的算法题目全部基于经典的《剑指 Offer（数据结构与算法面试题精讲）》。在如今竞争激烈的技术求职环境下，算法能力已成为前端开发岗位笔试考核的关键要点。通过深入钻研这一系列算法题，大家能够系统地积累算法知识和解题经验。每一道题目的分析与解答过程，都像是一把钥匙，为大家打开一扇通往高效编程思维的大门，帮助大家逐步提升自己在数据结构运用、算法设计与优化等方面的能力。
无论是即将踏入职场的应届毕业生，还是想要进一步提升自己技术水平的在职开发者，掌握扎实的算法知识都是提升竞争力的有力武器。希望大家能跟随我的步伐，在这个系列中不断学习、不断进步，为即将到来的前端笔试做好充分准备，顺利拿下心仪的工作机会！快来订阅吧，让我们一起开启这段算法学习之旅！