536.从字符串⽣成⼆叉树
Q:
A:
1.递归，左右边界做函数参数，太弟弟略过。
2.迭代，⿎捣了半天
题⽬给的字符串只看数字顺序的话是前序。那么想⼀下我们写⾮递归前序遍历时候，对于⼀个节点cur，如果不是空直接输出它的值，然后放到栈顶，再令cur=cur的左孩⼦进⾏循环。如果cur为空，那么令cur=栈顶的右孩⼦并pop栈顶并继续。
对于给定前序字符串，假如前三个数字是a、b、c，⾸先应该新建⼀个值为a的节点A（毕竟我们迭代只能从前向后不是？）。那么接下来对照⾮递归遍历，这时候我们应该输出它的值a再放到栈顶，再取其左节点，但我们这⾥是要⽤字符串建树。所以我们不⽤输出它的值，放到栈顶这⼀步是⼀样的。⽽由于字符串是前序，a后⾯紧接着的b就是a的左孩⼦，所以继续遍历数字b就好了。对于数字b我们建⽴节点B，这时栈顶就是B的⽗亲，所以我们把B和栈顶（也就是A）连起来，当然我们要查看⼀下栈顶（A）有⽆左孩⼦，没左孩⼦那么我们就把A的左孩⼦置为B，如果有左孩⼦了那么把A的右孩⼦置为B（因为之后遍历c的时候建⽴节点C还要和A相连，必须得判断⼀下）。
⽐较重要的⼀个地⽅：假设当前数字为x，这个数字x马上要新建节点X，栈顶始终存的是X的⽗亲。因为
字符串给的顺序是根-》左-》右，我们有理由认为，最先考察的跟⼀定先新建了节点并放在了栈顶，那么接下来的左孩⼦⼊栈后。出栈左孩⼦，（此时栈顶是左孩⼦的⽗亲），把左孩⼦和它爸连起来。之后右孩⼦再⼊栈。再出栈右孩⼦，栈顶还是⽗亲节点没有动，再把右孩⼦和⽗节点连起来。这时候，根节点为根的⼆叉树全部重构好了，此时根节点下⾯的节点就都隐藏了，它可以作为⼀个单独的节点，可能还有另⼀个节点P是它的⽗亲，但P是看不到之前根节点的孩⼦的，因为此时栈中只有之前的根节点，它的孩⼦们、孩⼦的孩⼦们都pop掉了。说的⽐较啰嗦，感觉我真不太适合当⽼师。。
2019年11⽉11⽇ 20:04:41
/**
* Definition for a binary tree node.
* struct TreeNode {
*    int val;
*    TreeNode *left;
*    TreeNode *right;
*    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* str2tree(string s) {
s+=')';
int len=s.size();二叉树中序遍历非递归算法
if(len==1){return 0;}
int flag=1,temp=0;
stack<TreeNode*> sta;
TreeNode* root=new TreeNode(0);
sta.push(root);
TreeNode* cur=0,*par=0;
for(int i=0;i<len;++i){
if(s[i]=='('){
;
}
else if(s[i]==')'){
p();
sta.pop();
p();
if(par->left){
par->right=cur;
}
else{
par->left=cur;
}
}
else if(s[i]=='-'){
flag=-1;
}
else{  //s[i]为数字
temp=temp*10+(s[i]-'0');
if(s[i+1]==')' or s[i+1]=='('){
cur=new TreeNode(temp*flag);                    sta.push(cur);
flag=1,temp=0;
}
}
}
return root->left;
}
};

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。