剑指offer之树专题
1、层次遍历（bfs)
非递归
每一层是按照从左到右的顺序
为了满足先遍历先出采用队列的数据结构,队列里面存放我们遍历过的节点
首先根节点入队，当队列不空时，出队队首元素并打印相应节点的内容。如果出队的节点有左孩子或者右孩子，则入队左孩子节点或者右孩子节点，如此循环
class Solution
{
public:
vector<int> bfs(TreeNode *root)//返回的是一个int的vector
{
vector<int>res;
queue<TreeNode *>q;//辅助队列
if(root==NULL)return res;//空树返回空
q.push(root);//将根节点入队
while(!q.empty())
{
//入队
res.push_back(q.front()->val);
if(q.front()->left!=NULL)
{
q.push(q.front()->left);
}
if(q.front()->right!=NULL)
{
q.push(q.front()->right);
}
// 出队
q.pop();//弹出第一个元素
}
return res;//只有最后才会执行这个
}
};2、深度优先遍历（递归）
按照遍历顺序将节点存放在容器中
遍历就像我们走路上有很多坑，一旦掉进去就是很多层，只有到底才能开始慢慢向上攀爬，小事件结束就是我们的梯子
1、确定终止条件
如果当层遍历的节点为空的话，就是结束本层，返回上一层
if(cur == NULL) return;2、单层递归的逻辑：前序是中、左、右
vec.push_back(cur ->val);//中间节点插入
traversal(cur ->left,vec);//左
traversal（cur ->right,vec）;//右完整代码
lass Solution {
public:
void preorder(TreeNode *root, vector<int> &res) {
if (root == nullptr) return;//终止条件
res.push_back(root->val); //中
preorder(root->left, res); //左
preorder(root->right, res); //右
}
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
preorder(root, res);
return res;
}
};
8非递归
利用栈
访问到空节点的话，就会跳到上一层，然后将栈顶出
我们栈是先进后出
前序是中，右、左（）
中序：左、中、右（）
后续：中、左、右
//前序代码
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
if(root == nullptr) return res;
s.push(root); //压入根结点
while (!s.empty()){ //入栈是 根右左
TreeNode* node = s.top(); s.pop();
res.push_back(node->val); //中
if (node->right) stk.push(node->right); //右
if (node->left) stk.push(node->left); //左
}
return res;
}
};