Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},1
\
2
/
3return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
這道題是讓用非遞歸的方式中序遍歷二叉樹。
仿照遞歸算法執行過程中遞歸工作站的狀態可見:
1. 當棧頂記錄中的指針非空時,應遍歷左子樹,即指向左子樹的指針入棧
2. 若棧頂記錄中的指針為空,則應退至上一層,若是從左子樹返回,則應訪問當前棧頂記錄中指針所指的根節點
3. 若是從右子樹返回,則 表明當前層的遍歷結束,應繼續退棧。
遍歷右子樹時不需要保存當前層的根指針,可以直接修改棧頂記錄中的指針即可。
下面貼出代碼,有兩種形式:
vector inorderTraverse(TreeNode* root){
vector ans;
stack s;
s.push(root);
TreeNode* p=s.top();
while(!s.empty()){
while(p){
s.push(p->left);
p=p->left;
}
s.pop();//空指針退棧
if(!s.empty()){
p=s.top();
ans.push_back(p->val);
s.pop();
s.push(p->right);
p=p->right;
}
}
return ans;
}
vector inorderTraverse(TreeNode* root){
vector ans;
if (root == NULL)
return ans;
stack s;
while (root|| !s.empty()){
if(root){
s.push(root);
root=root->left;
}else{
root=s.top();
ans.push_back(root->val);
s.pop();
root=root->right;
}
}
return ans;
}