数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中从先序遍历恢复树
假设有一棵二叉树。我们将对二叉树的根节点进行先序深度优先搜索。
在此遍历中的每个节点，输出将是 D 个短划线（其中 D 是该节点的深度），之后我们显示该节点的值。众所周知，如果一个节点的深度是 D，则其直接子节点的深度是 D+1，根节点的深度是 0。
我们还需要记住的一件事是，如果一个节点只有一个子节点，则该子节点保证是左子节点。因此，如果给定此遍历的输出 S，则恢复树并返回其根节点。
因此，如果输入类似于“1-2--3--4-5--6--7”，则输出将是
为了解决这个问题，我们将遵循以下步骤：
定义一个栈 st
i := 0，n := S 的大小
lvl := 0，num := 0
当 i < n 时，执行：
对于初始化 lvl := 0，当 S[i] 与 '-' 相同，更新（将 lvl 增加 1），（将 i 增加 1），执行：
不做任何事
num := 0
当 (i < n 且 S[i] 不等于 '-') 时，执行：
num := num * 10 + (S[i] - '0')
（将 i 增加 1）
当 st 的大小 > lvl 时，执行：
从 st 中删除元素
temp = 创建一个具有 num 值的新树节点
如果 st 不为空且 st 的顶部元素的左子节点不为空，则：
st 的顶部元素的左子节点 := temp
否则，当 st 不为空时：
st 的顶部元素的右子节点 := temp
将 temp 插入 st
当 st 的大小 > 1 时，执行：
从 st 中删除元素
返回（如果 st 为空，则返回 NULL，否则返回 st 的顶部元素）
让我们看看以下实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
stack<TreeNode*> st;
int i = 0;
int n = S.size();
int lvl = 0;
int num = 0;
while (i < n) {
for (lvl = 0; S[i] == '-'; lvl++, i++)
;
num = 0;
while (i < n && S[i] != '-') {
num = num * 10 + (S[i] - '0');
i++;
}
while (st.size() > lvl)
st.pop();
TreeNode* temp = new TreeNode(num);
if (!st.empty() && !st.top()->left) {
st.top()->left = temp;
}
else if (!st.empty()) {
st.top()->right = temp;
}
st.push(temp);
}
while (st.size() > 1)
st.pop();
return st.empty() ? NULL : st.top();
}
};
main(){
Solution ob;
TreeNode *root = ob.recoverFromPreorder("1-2--3--4-5--6--7");
inord(root);
}输入
"1-2--3--4-5--6--7"
输出
3 2 4 1 6 5 7
更新于: 2020-06-08
416 次查看
广告