LeetCode 94. Binary Tree Inorder Traversal 动态演示

佚名 5年前 (2019-08-06) 算法 1057人围观抢沙发百度已收录

非递归的中序遍历，要用到一个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()>0){
            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;
    }
};