二叉树的遍历总结

首先时关于二叉树的前序,中序,后序遍历的递归公式写法:

void order(TreeNode *tree, vector<int> &ans) {
    if (tree) {
        // ans.push_back(tree->val);  // 前序preorder
        postorder(tree->left, ans);
        // ans.push_back(tree->val);  // 中序inorder
        postorder(tree->right, ans);
        // ans.push_back(tree->val);  // 后序postorder
    }
}

vector<int> orderTraversal(TreeNode *root) {
    vector<int> ans;
    if (!root) return ans;
    postorder(root, ans);
    return ans;
}

关于这三者遍历的本质其实是一致的,每个节点均会在逻辑上被访问三次,前,中,后序遍历的区别便在于逻辑上前序遍历在第一次节点被访问时记录,中序遍历是在第二次访问时记录,后续遍历则是在第三次(如下图节点2所示,访问null节点也算一次,图中并未画出)

基于此我们不难写出前序遍历与中序遍历的非递归写法:

即任意节点入栈时即为逻辑上第一次访问,出栈即为第二次

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    
    stack<TreeNode*> st;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val); // 入栈时访问
        
        // 右子节点先入栈，左子节点后入栈
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    return result;
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* current = root;
    
    while (current != nullptr || !st.empty()) {
        // 将所有左子节点入栈
        while (current != nullptr) {
            st.push(current);
            current = current->left;
        }
        
        // 出栈时访问
        current = st.top();
        st.pop();
        result.push_back(current->val);
        
        // 转向右子节点
        current = current->right;
    }
    return result;
}

关于后序访问,对于一个需要进栈的元素,一个栈只能表示两种状态,我们需要在逻辑上第三次访问该节点时再记录该值,因此我们不妨再引入一个状态码,这样我们就有足够的状态能够标识逻辑上的第三次访问了

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    
    // 栈中存储节点和状态标记的pair
    // state = 0: 第一次访问，需要处理左右子树
    // state = 1: 第二次访问，左右子树已处理完，可以输出当前节点
    stack<pair<TreeNode*, int>> st;
    st.push({root, 0});
    
    while (!st.empty()) {
        auto [node, state] = st.top();
        st.pop();
        
        if (state == 0) {
            // 第一次访问该节点，将状态改为1后重新压栈
            st.push({node, 1});
            
            // 先压右子树（后处理），再压左子树（先处理）
            // 确保实际遍历顺序为：左 -> 右 -> 根
            if (node->right) st.push({node->right, 0});
            if (node->left) st.push({node->left, 0});
        } else {
            // 第二次访问，此时左右子树都已处理完毕，输出当前节点
            result.push_back(node->val);
        }
    }
    
    return result;
}

另外还有一种实现方法,即使用双栈,这样同样拓展了状态实现第三次访问时记录,但此方法思路更加巧妙一点.

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    
    stack<TreeNode*> st1, st2;
    st1.push(root);
    
    // st1按根-右-左顺序弹出，st2接收，最后从st2弹出即为左-右-根
    while (!st1.empty()) {
        TreeNode* node = st1.top();
        st1.pop();
        st2.push(node);
        
        if (node->left) st1.push(node->left);
        if (node->right) st1.push(node->right);
    }
    
    while (!st2.empty()) {
        result.push_back(st2.top()->val);
        st2.pop();
    }
    return result;
}

以上所有遍历实现时间复杂度与空间复杂度均为O(n).

最后是关于二叉树的层序遍历,这个没什么好多说的,使用队列对每层进行显示存储再按序访问即可.

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size(); // 当前层的节点数量
        vector<int> currentLevel;
        
        // 处理当前层的所有节点(注意不能使用!q.empty()作为判断依据)
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);
            
            // 将下一层的子节点加入队列
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        result.push_back(currentLevel);
    }
    
    return result;
}