二叉树先序遍历三种方法

二叉树先序遍历三种方法

一、递归写法

// 这个是偷懒不想多拆分函数
class Solution {
public:
    vector<int> tree;
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return tree;
        tree.push_back(root->val);
        if(root->left)
            preorderTraversal(root->left);
        if(root->right)
            preorderTraversal(root->right);
        return tree;
    }
};
// 同理有搬运过来更优解
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    preTraversal(root, v);
    return v;
}
void preTraversal(TreeNode* root, vector<int>& v){
    if(!root) return;
    v.push_back(root->val);
    preTraversal(root->left, v);
    preTraversal(root->right, v);
}

二、迭代写法

// 迭代,搬运过来的,使用栈模拟递归写法
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    if(!root) return v;
    TreeNode* temp = root;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty()){
        temp = s.top();
        s.pop();
        v.push_back(temp->val);
        if(temp->right) s.push(temp->right);
        if(temp->left) s.push(temp->left);
    }
}

三、Morris 遍历

同样是搬运过来的。

// 空间复杂度 O(1)
vector<int> preorderTraversal(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){
                v.push_back(temp->val);
                prev->right = temp;
                temp = temp->left;
            }else{
                prev->right = NULL;
                temp = temp->right;
            }
        }
    }
}

中序遍历
后序遍历

发表评论

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