二叉树的遍历

前言

二叉树的遍历是二叉树的基础算法，本文对个人的遍历写法做个记录

深度优先遍历

递归写法

递归遍历比较简单，不作讲解和注释

// 前序遍历
void preorder(Node* node) {
    if (node) {
        visit(node);
        preorder(node->left);
        preorder(node->right);
    }
}

// 中序遍历
void inorder(Node* node) {
    if (node) {
        inorder(node->left);
        visit(node);
        inorder(node->right);
    }
}

// 后序遍历
void postorder(Node* node) {
    if (node) {
        postorder(node->left);
        postorder(node->right);
        visit(node);
    }
}

非递归写法

三种遍历的非递归写法难以统一的原因是在栈的遍历过程中，在处理当前节点时还需要指针去索引另一个访问节点，这里记录一个统一的迭代写法，将两种节点都放入栈中，但是在处理的当前节点后放入一个null与访问节点区分，这种写法在三种遍历上只需要改动顺序

前序遍历

vector<Node*> preorder(Node* root) {
    vector<Node*> res;
    stack<Node*> stack;
    if (root) stack.push(root);
    while (!stack.empty()) {
        // 当前节点
        Node* node = stack.top();
        // 该节点是访问节点
        if (node) {
            stack.pop();
            // 从左到右，左节点在栈顶，先放入右节点
            if (node->right) stack.push(node->right);
            if (node->left) stack.push(node->right);
            
            // 前序遍历，根节点在栈顶
            stack.push(node);
            // 添加null，使访问节点变为处理节点，即下次访问到null，将该节点放入结果集
            stack.push(nullptr);
        } else {
            // 遇到null，则栈顶下一个元素是处理节点
            stack.pop();
            // 获取处理节点
            node = stack.top();
            stack.pop();
            res.push_back(node);
        }
    }
    return res;
}

中序遍历

vector<Node*> inorder(Node* root) {
    vector<Node*> res;
    stack<Node*> stack;
    if (root) stack.push(root);
    while (!stack.empty()) {
        Node* node = stack.top();
        if (node) {
            stack.pop();
            if (node->right) stack.push(node->right);
            if (node->left) stack.push(node->left);
            stack.push(node);
            stack.push(nullptr);
        } else {
            stack.pop();
            node = stack.top();
            stack.pop();
            res.push_back(node);
        }
    }
    return res;
}

后序遍历

vector<Node*> postorder(Node* root) {
    vector<Node*> res;
    stack<Node*> stack;
    if (root) stack.push(root);
    while (!stack.empty()) {
        Node* node = stack.top();
        if (node) {
            stack.pop();
            stack.push(node);
            stack.push(nullptr);
            if (node->right) stack.push(node->right);
            if (node->left) stack.push(node->left);
        } else {
            stack.pop();
            node = stack.top();
            stack.pop();
            res.push_back(node);
        }
    }
    return res;
}

层次遍历

层次遍历写法较简单，要注意它的应用，灵活变化

非递归写法

vector<vector<Node*>> levelorder(Node* root) {
    queue<Node*> q;
    // 每一层是一个vector
    vector<vector<Node*>> res;
    if (root) q.push(root);
    while (!q.empty()) {
        // 当前层宽度
        int size = q.size();
        vector<Node*> level;
        for (int i = 0; i < size; i++) {
            Node* node = q.front();
            q.pop();
            level.push_back(node);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

递归写法

使用前序遍历，通过深度索引到相应的层数组再添加，根节点的深度为0

void levelorder(Node* node, vector<vector<Node*>>& res, int depth) {
    if (!node) return;
    // 到达最后一层的下一层时，若还有节点，创建数组
    if (res.size() == depth) res.push_back(new vector<Node*>());
    res[depth].push_back(node);
    levelorder(node->left, res, depth + 1);
    levelorder(node->right, res, depth + 1);
}

vector<vector<Node*>> level(Node* root) {
    vector<vector<Node*>> res;
    levelorder(root, res, 0);
    return res;
}