leetcode/94BinaryTreeInorderTraversal

Binary Tree Inorder Traversal

这个问题用递归非常好解决, 但是作者要求使用迭代

这是一个以迭代实现子树遍历的做法, 值得做一下笔记

my solution

一开始我没看到 follow up, 然后用递归解决了

之后看到的时候没什么好的思路

(有部分是受了答案的影响, 因为这时候我已经解决了, 可以看别人的答案了)

(不得不说答案真是害人啊… 如果我独立思考的话, 花一部分时间也能想通的)

后面借鉴了答案的思想, 自己实现了, 所以这里就不贴出来了

best solution (4ms)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode *curr; 
        stack<TreeNode*> st; 
        curr = root;
        vector<int> res; 

        while ( !st.empty() || curr ){
            while ( curr ) { st.push(curr); curr = curr->left; }
            curr = st.top();
            st.pop();
            res.push_back(curr->val);
            curr=curr->right;
        }
        return res;
    }
};

简单来说

1. 遍历所有左子树
2. 获得栈顶, 存值, 然后以其右子树继续遍历

重复以上步骤, 很简单吧 (但是我当时为什么没有想出来呢 ? …)

以同样的逻辑, 可以实现 leftorder, rightorder

(如果没记错的话, 应该是这么叫的, 而且如果没估计错的话, 应该可以)