1028. 从先序遍历还原二叉树

1028. 从先序遍历还原二叉树

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

示例 1：

输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]

示例 2：

输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]

示例 3：

输入："1-401--349---90--88"
输出：[1,401,null,349,88,90]

提示：

• 原始树中的节点数介于 1 和 1000 之间。
• 每个节点的值介于 1 和 10 ^ 9 之间。

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 using namespace std;
  6 
  7 /**
  8     Definition for a binary tree node.
  9  */
 10 struct TreeNode {
 11     int val;
 12     TreeNode *left;
 13     TreeNode *right;
 14     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 15     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 16     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 17 };
 18 
 19 class Solution {
 20 public:
 21     TreeNode* recoverFromPreorder(string traversal) {
 22         stack s; // 存储树节点
 23         TreeNode *root = nullptr;
 24 
 25         unsigned int depth = 0; // 树节点的深度
 26         unsigned int index = 0;
 27         while (index < traversal.size()) {
 28             // 根据字符串中'-'个数找出当前节点的深度
 29             if (traversal[index] == '-') {
 30                 depth++;
 31                 index++;
 32                 continue;
 33             }
 34             int val = 0;
 35             // 根据字符串中数字找到当点节点值
 36             while (index < traversal.size() && isdigit(traversal[index])) {
 37                 val = val * 10 + (traversal[index] - '0');
 38                 index++;
 39             }
 40             // 如果深度小于当前节点的深度,则说明它是某个节点的右节点
 41             while (depth < s.size() && s.size() > 0) {
 42                 s.pop();
 43             }
 44             TreeNode *tmpNode = new TreeNode(val);
 45             if (s.size() <= 0) {
 46                 root = tmpNode;
 47                 s.push(root);
 48             } else if (s.top()->left == nullptr) {
 49                 s.top()->left = tmpNode;
 50                 s.push(s.top()->left);
 51             } else if (s.top()->right == nullptr) {
 52                 s.top()->right = tmpNode;
 53                 s.push(s.top()->right);
 54             }
 55             depth = 0;
 56         }
 57         return root;
 58     }
 59 
 60     void preOrderPrint(TreeNode *root) {
 61         if (root == nullptr) {
 62             return;
 63         }
 64         vector<int> res;
 65         stack s;
 66         s.push(root);
 67         while (!s.empty()) {
 68             TreeNode *tmp = s.top();
 69             s.pop();
 70             res.push_back(tmp->val);
 71             if (tmp->right != nullptr) {
 72                 s.push(tmp->right);
 73             }
 74             if (tmp->left != nullptr) {
 75                 s.push(tmp->left);
 76             }
 77         }
 78         for (auto &val : res) {
 79             cout << val << " ";
 80         }
 81         cout << endl;
 82         return;
 83     }
 84     void midOrderPrint(TreeNode *root) {
 85         if (root == nullptr) {
 86             return;
 87         }
 88         vector<int> res; // 保存中序遍历节点值
 89         stack s;
 90         TreeNode *p = root;
 91         while (!s.empty() || p != nullptr) {
 92             while (p != nullptr) {
 93                 s.push(p);
 94                 p = p->left;
 95             }
 96             if (!s.empty()) {
 97                 p = s.top();
 98                 s.pop();
 99                 res.push_back(p->val);
100                 p = p->right;
101             }
102         }
103         for (const auto &val : res) {
104             cout << val << ' ';
105         }
106         cout << endl;
107         return;
108     }
109     void postOrderPrint(TreeNode *root) {
110         if (root == nullptr) {
111             return;
112         }
113         stack s;
114         vector<int> res;
115         s.push(root);
116         TreeNode *p;
117         while (!s.empty()) {
118             p = s.top();
119             s.pop();
120             res.push_back(p->val);
121             if (p->left != nullptr) {
122                 s.push(p->left);
123             }
124             if (p->right != nullptr) {
125                 s.push(p->right);
126             }
127         }
128         reverse(res.begin(), res.end());
129         for (const auto &val : res) {
130             cout << val << ' ';
131         }
132         cout << endl;
133         return;
134     }
135 };
136 
137 int main()
138 {
139     string s = "1-2--3--4-5--6--7";
140     Solution *test = new Solution();
141     TreeNode *root = test->recoverFromPreorder(s);
142     cout << "pre order print:" << endl;
143     test->preOrderPrint(root);
144     cout << "mid order print:" << endl;
145     test->midOrderPrint(root);
146     cout << "post order print:" << endl;
147     test->postOrderPrint(root);
148     system("pause");
149     return 0;
150 }

测试运行结果：