LeetCode 94: Binary Tree Inorder Traversal 解题与思考
LeetCode 94: Binary Tree Inorder Traversal 解题与思考
[原题链接]
题目描述
实现非递归的树的中序遍历
思路
当然也还是和之前的后序遍历一样要用到栈,这次将节点输出的时间是访问其右子树之前。
而当我们在栈中找到一个节点时,它很明显是之前被我们访问过,并在访问左子树之前压栈的;那么我们只要选择在需要用到栈顶元素时输出就好。
算法
前期准备:一个节点栈,一个答案数组
1、对于一个节点,将其入栈,将当前节点设为其左子节点
2、当前节点为空,若
栈顶节点无右子节点
那么其为一个叶子节点,直接将栈顶元素输出后出栈栈顶节点有右子节点
那么就将栈顶元素输出后出栈,并将当前节点设为该右子节点
代码
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
TreeNode *nowNode = root;
vector<int> result;
stack<TreeNode*> treeStack;
while ( nowNode || !treeStack.empty() ) {
if ( nowNode ) {
treeStack.push(nowNode);
nowNode = nowNode->left;
}
else {
TreeNode *topNode = treeStack.top();
if ( topNode->right /*&& lastNode != topNode */) {
result.push_back(topNode->val);
nowNode = topNode->right;
treeStack.pop();
}
else {
result.push_back(treeStack.top()->val);
treeStack.pop();
}
}
}
return result;
}
};
思考
相比前序遍历,稍微要转一下,不过也就一下下
原文地址:http://blog.csdn.net/cjl707408282/article/details/78199237