30 Day Challenge Day 20 | Leetcode 94. Binary Tree Inorder Traversal

题解

Medium

Tree, Stack

几天之内再次做了一遍，思路依旧会卡壳。看来在栈的运用上还是一个难点，毕竟这个倒序的数据结构比起队列并不如那么直观。不过还是很重要。

思路就是先把左节点依次压入栈中，直到最左边的节点，那么以当前节点为根节点，排序就比较容易了，这和遍历方向是一致的所以，可以把当前节点直接放进结果数组中，然后再移动到右节点，，重复上面过程。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;

        stack<TreeNode*> st;
        
        TreeNode* node = root;
        
        while(node || !st.empty()) {
            TreeNode* temp = node;
            while(temp) {
                st.push(temp);
                temp = temp->left;
            }
            TreeNode* t = st.top();
            st.pop();
            ret.push_back(t->val);
            node = t->right;
        }
        
        return ret;
    }
};