二叉树层序遍历
class Solution {
public:
queue<TreeNode*> ready;//队列中放入准备要记录的节点
vector<vector<int>> res;//存储最终输出的结果
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root)//如果这个树是空的就直接结束
{
return res;
}
ready.push(root);//先把根节点放进队列中
while(!ready.empty())//如果队列中没有要记录的节点就结束循环
{
int centerSize = ready.size();//记录每一层节点的数量
vector<int> temp;//用来临时存储这一层的节点值
for(int i =0;i<centerSize;i++)//把上一层结点全部pop出去 保证下一次循环是第二层
{
auto center = ready.front();//从队列第一个取出要遍历的节点
ready.pop();//将给结点从队列中删除
temp.push_back(center->val);
if(center->left)//如果有左子树就将该左子树放进队列 并且将值压入栈中
{
ready.push(center->left);
//temp.push_back(center->left->val);
}
if(center->right)
{
ready.push(center->right);
//temp.push_back(center->right->val);
}
}
res.push_back(temp);
}
return res;
}
};
/*
迭代实现
bfs
递归实现层序遍历
子问题就是把根节点的左右子树压入栈中
用一个队列表示要被遍历的根节点 压完一个就弹出一个
这一层要做什么 层数+1 把这一层的val压入栈
要返回什么 是否有左右子树了 有返回true 没有返回false
终止条件是什么 这一层都没有左右子树了
*/
二叉树中序遍历
class Solution {
public:
vector<int> res;
int mid(TreeNode* node)
{
if(node == nullptr)
return 0;
mid(node->left);
res.push_back(node->val);
mid(node->right);
return 0;
};
vector<int> inorderTraversal(TreeNode* root) {
mid(root);
return res;
}
};
/*
递归遍历 中序遍历 左 根 右
这一节要做什么 输出当前结点的值
终止条件是什么 如果是空节点就结束
返回给上一级什么 未知
void mid(TreeNode* node)
{
if(node == null)
return 0;
mid(node->left);
cout<<node->val;
mid(node->right);
}
*/
二叉树后续遍历
迭代版本
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> res;
if(root == NULL)
return res;
//s.push(root);
TreeNode* pre = NULL;
while(root!=NULL||!s.empty())
{
while(root!= NULL)
{
s.push(root);
root = root->left;
}
root = s.top();//此时获取的是上面root结点的最左边那个结点
//s.pop();
if(root->right!= NULL&&root->right!= pre)//如果这个节点有右结点就把右结点放进去
{
//s.push(root);
root = root->right;
}
else
{
pre = root;
res.push_back(root->val);
s.pop();
root = NULL;
}
/*一个结点什么时候才能被读取入res 要么他是叶子节点 要么就是他的左右结点都被读过了 也就是 右边结点是上一个结点*/
//res.push_back(root->val);
}
return res;
}
};
二叉树前序遍历
class Solution {
public:
vector<int> res;
void cersion(TreeNode* root)
{
if(!root)
{
return;
}
res.push_back(root->val);
cersion(root->left);
cersion(root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
cersion(root);
return res;
}
};
前序中序生成二叉树
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
for(int i = 0; i < inorder.size(); i++)
dic[inorder[i]] = i;
return recur(0, 0, inorder.size() - 1);
}
private:
vector<int> preorder;
unordered_map<int, int> dic;
TreeNode* recur(int root, int left, int right) { //root是根节点的位置 left和right是该区间的左右范围 这些都是先序遍历中的
if(left > right) return nullptr; // 递归终止
TreeNode* node = new TreeNode(preorder[root]); // 建立根节点
int i = dic[preorder[root]]; // 划分根节点、左子树、右子树
node->left = recur(root + 1, left, i - 1); // 开启左子树递归
node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
};
/*这道题用递归的原因是可以吧先序遍历看成很多个子问题 先序遍历可以知道根节点是哪个(每个区间的第一个就是根节点) 而中序遍历可以通过根节点的位置知道左右子树的节点数量 中序遍历中 根节点左边就是左子树 右边就是右子树 通过这个数量可以吧先序遍历不断的划分成更小的数组(根节点/左子树/右子树)*/
二叉搜索树后序遍历
class Solution {
public:
unordered_map<int,int>map;
vector<int> postorder;
bool recurser(int root,int left,int right,vector<int> &inOrder)
{
/*中序遍历中postorderroot的位置 */
if(root<0)
return true;
int i = map[postorder[root]];
int rightNum = right - i;
int leftNum = i-left;
if(left >= right)
return true;
for(int j = root-1;j>(root-rightNum);j--)
{
if(postorder[j]<postorder[root])
return false;
}
for(int j = (root-rightNum-1);j>root-rightNum-1-leftNum;j--)
{
if(postorder[j]>postorder[root])
return false;
}
/*右子树*/
return recurser(root-1,i+1,right,inOrder)&&recurser(root - rightNum-1,left,i-1,inOrder);
}
bool verifyPostorder(vector<int>& postorder) {
this->postorder =postorder;
int size = postorder.size();
vector<int> inOrder = postorder;
sort(inOrder.begin(),inOrder.end());
for(int i = 0;i<size;i++)
{
map[inOrder[i]] = i;
}
return recurser(size-1,0,size-1,inOrder);
}
};
/*最后一个一定是根
一个后续遍历是无法建立一棵树的 所以不可能生成中序遍历 而且他也没有给树的结构体 说明肯定不要建树 那么 等下 我可以获得中序遍历 从小到大排列一下 那我现在就有后续遍历和中序遍历 那么我
*/
/*
1 3 2 6 5 后续遍历特点 最后一个一定是根节点 紧贴他的那个一定是右结点 那么
1 2 3 5 6 中序遍历特点 通过根节点的位置知道左右子树的数量 那么先知道5 说明左子树3个 有子树1个
1 6 3 2 5
1 2 3 5 6
一样的
*/
/*
递归
left right root
这一层我们要做什么root = postorder[right]
i = map[root];
if(i!=right)//就说明有右子树
if(map[postorder[right-1]] < map[]postorder[right] )
return false;
右子树recurser(root-1,right + right -i-1,root-1,)
左子树recurser(root-right + i,left,root-right + i)
*/
