leetcode 1028. Recover a Tree From Preorder Traversal

本文主要是介绍leetcode 1028. Recover a Tree From Preorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode 1028. Recover a Tree From Preorder Traversal

题意：给一个二叉树的深度优先的前序遍历，重建一颗二叉树。

输入："1-2--3--4-5--6--7"

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

思路：主要的难点是5的父节点是1，这里考虑用stack保存，当前节点以及节点所在的层数。

通过更新栈顶元素，来找当前点的父节点。

代码：

class Solution {
public:TreeNode* recoverFromPreorder(string S) {int num = 0;int num_ = 0;TreeNode* root;stack<pair<TreeNode*, int>> s;for (int i = 0; i<S.size(); i++){if (S[i] != '-'){num = num * 10 + S[i] - '0';if (i == S.size() - 1 || S[i+1] == '-'){//cout<<num_<<'-'<<num<<endl;if (s.empty()){TreeNode* now = new TreeNode(num);root = now;s.push(make_pair(now, 0));}else{while (!s.empty()){if (s.top().second != num_ - 1)s.pop();elsebreak;}TreeNode* father = s.top().first;TreeNode* now = new TreeNode(num);s.push(make_pair(now, num_));if (father->left == nullptr)father->left = now;elsefather->right = now;}num = 0;num_ = 0;}}else if (S[i] == '-'){num_++;}}return root;}
};

 

这篇关于leetcode 1028. Recover a Tree From Preorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---