一、题目介绍
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3
输出: [1,3,2] 进阶: 递归算法很简单,你可以通过迭代算法完成吗?
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
本题采用迭代方法,利用栈来模拟递归调用,具体详见代码。
三、解题代码
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> vec;
if(root == NULL)
return vec;
else
{
stack<TreeNode*> st;
TreeNode* ptemp = root;
while(ptemp || !st.empty())
{
//左子树遍历到叶子节点
while(ptemp)
{
st.push(ptemp);
ptemp = ptemp->left;
}
if(!st.empty())
{
ptemp = st.top();
vec.push_back(ptemp->val);
st.pop();
ptemp = ptemp->right;
}
}
}
return vec;
}
};
四、解题结果