题目链接：leetcode94
题目大意
给定一个二叉树，返回它的中序 遍历。 非递归实现
解题思路
栈+模拟
大致的思路就是不断往左子树切换，直到左边为空后把当前的节点输出，然后转到右子树。如果右子树为空说明需要回溯，弹栈即可。
代码实现
class Solution {
public:
vector
<int> inorderTraversal(TreeNode
* root
) {
vector
<int> res
;
stack
<TreeNode
*> stk
;
TreeNode
*curpoint
= root
;
while (curpoint
) {
if (curpoint
->left
) {
stk
.push(curpoint
);
curpoint
= curpoint
->left
;
} else {
res
.push_back(curpoint
->val
);
if (curpoint
->right
) {
curpoint
= curpoint
->right
;
} else {
curpoint
= NULL;
}
}
while (!curpoint
&& !stk
.empty()) {
res
.push_back(stk
.top()->val
);
curpoint
= stk
.top()->right
;
stk
.pop();
}
}
return res
;
}
};
