LeetCode 94. Binary Tree Inorder Traversal 动态演示

非递归的中序遍历，要用到一个stack

class Solution {

public:

    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> ret;

        if(!root)

            return ret;

        //a(ret)

        stack<TreeNode*> stk;

        stk.push(root);

        //ahd(root)

        //a(stk)

        //dsp

        TreeNode* p=root;

        while(p->left){

            stk.push(p->left);

            p=p->left;

            //dsp

        }

        while(stk.size()>){

            TreeNode* cur=stk.top(); stk.pop();

            ret.push_back(cur->val);

            //a(cur)

            //lk("root", cur)

            //dsp

            if(cur->right){

                stk.push(cur->right);

                p=cur->right;

                //dsp

                while(p->left){

                    stk.push(p->left);

                    p=p->left;

                    //dsp

                }

            }

        }

        return ret;

    }

};

程序动态运行结果： http://simpledsp.com/FS/Html/lc94.html