二叉树的中序遍历-三种方式

二叉树中序遍历三种方法

// 递归遍历
vector<int> v;
vector<int> inorderTraversal(TreeNode* root) {
    if(!root) return v;
    inorderTraversal(root->left);
    v.push_back(root->val);
    inorderTraversal(root->right);
    return v;
}


// 使用栈的迭代
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> v;
    if(!root) return v;
    TreeNode* temp = root;
    stack<TreeNode*> s;
    while(true){
        while(temp){
            s.push(temp);
            temp = temp->left;
        }
        if(s.empty()) break;
        temp = s.top();
        s.pop();
        v.push_back(temp->val);
        temp = temp->right;
    }
    return v;
}


// 迭代 morris traversal,无栈
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> v;
    if(!root) return v;
    TreeNode* temp = root, *prev;
    while(temp){
        if(!temp->left){
            v.push_back(temp->val);
            temp = temp->right;
        }else{
            prev = temp->left;
            while(prev->right&&(prev->right != temp))
                prev = prev->right;
            if(!prev->right){
                prev->right = temp;
                temp = temp->left;
            }else{
                v.push_back(temp->val);
                prev->right = NULL;
                temp = temp->right;
            }
        }
    }
}
// 三个方法来自 leetcode

先序遍历
后序遍历

发表评论

电子邮件地址不会被公开。 必填项已用*标注