徐州网站开发服务,制定推广方案,保定网站建设方案推广,网站后台管理是什么文章目录1. 题目2. 栈解题1. 题目
我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处#xff0c;我们输出 D 条短划线#xff08;其中 D 是该节点的深度#xff09;#xff0c;然后输出该节点的值。#xff08;如果节点的深度为 D#xff0c;则其…
文章目录1. 题目2. 栈解题1. 题目
我们从二叉树的根节点 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 之间。
来源力扣LeetCode 链接https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 栈解题
用一个栈存储pairTreeNode*, depth将节点和其深度不断地压栈但是当前节点的深度depth 栈顶的说明需要往上面找父节点所以弹栈找到深度比我小的即是父节点优先接在左节点
class Solution {
public:TreeNode* recoverFromPreorder(string S) {int depth 0, i 0, val 0;stackpairTreeNode*,int stk;TreeNode *root, *cur;val getVal(S,i);root new TreeNode(val);stk.push(make_pair(root,0));while(i S.size()){depth getDep(S,i);val getVal(S,i);cur new TreeNode(val);while(stk.top().second depth)stk.pop();if(stk.top().first-left)stk.top().first-right cur;elsestk.top().first-left cur;stk.push(make_pair(cur,depth));}return root;}int getVal(string S, int i)//获取数字{int val 0;while(i S.size() isdigit(S[i]))val val*10S[i]-0;return val;}int getDep(string S, int i)//获取深度{int depth 0;while(S[i] -){depth;i;}return depth;}
};
