【先序遍历 深度优先搜索】1028. 从先序遍历还原二叉树

本文涉及知识点

先序遍历
深度优先搜索汇总

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

我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处，我们输出 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 之间。

深度优先搜索

读取第一个数作为root，然后深度优先。
DFS(Vector pars,const string& s ,int iPos )
cnt 等于-的数量。
num的后面的值
{ p a r s 出栈，直到 c n t 等于 p a r s . s i z e ( ) p a r s [ c n t − 1 ] − > r i g h t 是当前节点 c n t < p a r s . s i z e ( ) p a r s [ c n t − 1 ] − > l e f t 是当前节点 c n t = = p a r s . s i z e ( )

{pars出栈，直到cnt等于pars.size()pars[cnt−1]−>right是当前节点pars[cnt−1]−>left是当前节点​​cnt<pars.size()cnt==pars.size()​

代码

class Solution {
public:
	TreeNode* recoverFromPreorder(string traversal) {
		int num = 0;
		int pos = 0;
		for (; isdigit(traversal[pos]); pos++) {
			num = num * 10 + (traversal[pos] - '0');
		}
		TreeNode* root = new TreeNode(num);
		vector< TreeNode*> pars;
		pars.emplace_back(root);
		DFS(pars, traversal, pos);
        return root;
	}
	void DFS(vector< TreeNode*>& pars, const string traversal, int pos) {
        if (pos >= traversal.length()) {return ;}	
		int cnt = 0;
		for (; '-' == traversal[pos]; pos++,cnt++);
		int num = 0;
		for (; (pos < traversal.length()) &&  isdigit(traversal[pos]); pos++) {
			num = num * 10 + (traversal[pos] - '0');
		}
		TreeNode* node = new TreeNode(num);
		if (pars.size() == cnt) {
			pars.back()->left = node;
		}
		else {
			while (pars.size() > cnt) {
				pars.pop_back();
			}
			pars.back()->right = node;
		}
		pars.push_back(node);
        DFS(pars, traversal, pos);			
	}
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。