【堆的使用】【dfs构建数】二叉树遍历

原题链接

方法一：

利用dfs构建树

因为这个前序遍历给了我们空的叶节点
所以我们可以只根据叶节点 构建树

abc##de#g##f

构建图如下

我们根据前序
abc##de#g##f

发现 dfs左子树 和 右子树
当出现#返回输出该父节点

继续递归右子树【但是我们发现如果继续递归右子树，得到的k还是左子树的位置的k】

所以我们在发现#时，需要将k++再返回具体如下代码

#include<iostream>using namespace std;string s;
int k;void dfs()
{if(s[k]=='#'){k++;return;}char ss = s[k++];dfs();cout << ss << ' ';dfs();
}int main()
{cin >> s;dfs();return 0;
}

方法二：利用堆的性质

abc##de#g##f
我们根据样例发现
遍历字符串，每次入堆
当出现#时，输出堆顶元素即可就是 中序遍历

#include<iostream>
#include<stack>using namespace std;string s;
stack<char> st;int main()
{cin >> s;for(int i = 0; i < s.size(); i++){if(s[i]=='#' && st.size()){cout << st.top() << ' ';st.pop();continue;}if(s[i]!='#'){st.push(s[i]);}}return 0;
}