当前位置： 首页 > article >正文

[LeetCode] 二叉树 I — 深度优先遍历（前中后序遍历） | 广度优先遍历（层序遍历）：递归法迭代法

article 2025/2/6 21:11:30

二叉树

  • 基础知识
  • 深度优先遍历
    • 递归法
    • 迭代法（栈）
    • 144# 二叉树的前序遍历
    • 94# 二叉树的中序遍历
    • 145# 二叉树的后序遍历
  • 广度优先遍历
    • 递归法
    • 迭代法（队列）
    • 102# 二叉树的层序遍历
    • 107# 二叉树的层序遍历 II
    • 199# 二叉树的右视图
    • 637# 二叉树的层平均值
    • 429# N叉树的层序遍历
    • 515# 在每个树行中找最大值
    • 116# 填充每个节点的下一个右侧节点指针
    • 117# 填充每个节点的下一个右侧节点指针 II
    • 104# 二叉树的最大深度
    • 111# 二叉树的最小深度
  • 补充知识：递归
    • 汉诺塔

基础知识

存储方式：数组顺序存储 / 指针链式存储

顺序存储：节点i的左孩子2i+1 、右孩子2i+2、父节点(i-1)/2

链式存储：

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	
	TreeNode(int x) : val(x), left(NULL), right(NULL) { }
}

完全二叉树：除底层外每层节点数都达到最大，底层节点集中在左边，包括满二叉树

满二叉树：深度为k的满二叉树有2^k-1个节点（1 2 ... 2^(k-1)）

二叉搜索树：有序树，左子树<根节点<右子树，查找、插入、删除时间复杂度均为 O(logn)，最坏情况为O(n)

平衡二叉树：左右子树的高度差（平衡因子）不超过1，避免树的高度过大以确保操作的时间复杂度稳定在 O(logn)

平衡二叉搜索树：AVL树、红黑树、Treap

AVL 树

  • 严格平衡（平衡因子 ≤ 1）
  • 优点：查询效率极高（严格 O(logn)）
  • 缺点：插入/删除可能需要频繁旋转，维护成本高

红黑树

  • 近似平衡（最长路径不超过最短路径的 2 倍）
  • 优点：插入/删除性能更优，适合频繁修改的场景
  • 应用：C++ std::map、Java TreeMap、数据库索引

Treap

  • 结合二叉搜索树和堆的性质，通过随机优先级维护平衡

深度优先遍历 借助栈实现

  • 前序遍历：中左右

  • 中序遍历：左中右

  • 后序遍历：左右中

广度优先遍历 借助队列实现

  • 层次遍历：逐层从左到右访问所有节点

深度优先遍历

递归法

// 前序遍历
void preorder(TreeNode *root, vector<int> &vec) {
    if (root == nullptr) return;
    vec.push_back(root->val);
    preorder(root->left, vec);
    preorder(root->right, vec);
}

// 中序遍历
void inorder(TreeNode *root, vector<int> &vec) {
    if (root == nullptr) return;
    inorder(root->left, vec);
    vec.push_back(root->val);
    inorder(root->right, vec);
}

// 后序遍历
void postorder(TreeNode *root, vector<int> &vec) {
    if (root == nullptr) return;
    postorder(root->left, vec);
    postorder(root->right, vec);
    vec.push_back(root->val);
}

迭代法（栈）

沿着递归实现依靠调用栈的思想，利用栈实现前中后序遍历

// 前序遍历：中入出右左入出-->中左右
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root == nullptr) return result;
    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 *cur = root;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) { // 深度遍历左子节点
            st.push(cur);
            cur = cur->left;
        } else {
            cur = st.top();
            result.push_back(cur->val);
            st.pop();
            cur = cur->right; // 访问根节点并弹出后再访问右子节点
        }
    }
    return result;
}

// 后序遍历：中入出左右入出-->中右左--reverse-->左右中
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root == nullptr) return result;
    st.push(root);
    while (!st.empty()) {
        TreeNode *node = st.top();
        result.push_back(node->val);
        st.pop();
        if (node->left) st.push(node->left);
        if (node->right) st.push(node->right);
    }
    reverse(result.begin(), result.end());
    return result;
}

以上三种遍历方法并不统一，前后序遍历用栈遍历，而中序遍历用指针遍历，因为栈无法解决访问节点和处理节点不一致的情况

通过为节点作标记统一迭代法：1. 空指针标记法；2. boolean标记法

// 中序遍历--空指针标记法
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root == nullptr) return result;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        if (node != nullptr) { // 检查空指针标记，右中左顺序入栈
            if (node->right) st.push(node->right);
            st.push(node);
            st.push(nullptr);
            if (node->left) st.push(node->left);
        } else {
            node = st.top();
            result.push_back(node->val);
            st.pop();
        }
    }
    return result;
}

// 中序遍历--boolean标记法
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<pair<TreeNode*, bool>> st;
    if (root == nullptr) return result;
    st.push(make_pair(root, false));
    while (!st.empty()) {
        auto node = st.top().first;
        auto visited = st.top().second;
        st.pop();
        if (!visited) { // 检查boolean标记，右中左顺序入栈
            if (node->right) st.push(make_pair(node->right, false));
            st.push(make_pair(node, true));
            if (node->left) st.push(make_pair(node->left, false));
        } else {
            result.push_back(node->val);
        }
    }
    return result;
}

144# 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

**输入：**root = [1,null,2,3]

输出：[1,2,3]

解释：

img

示例 2：

**输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

解释：

img

示例 3：

**输入：**root = []

输出：[]

示例 4：

**输入：**root = [1]

输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
// 递归法
// O(n) 0ms; O(n) 10.84MB
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void preorder(TreeNode *root, vector<int> &vec) {
        if (root == nullptr) return;
        vec.push_back(root->val);
        preorder(root->left, vec);
        preorder(root->right, vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorder(root, result);
        return result;
    }
};

空间复杂度 O(n)为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状为O(n)

迭代法：先将根节点入栈，根节点出栈后使其右子节点和左子节点入栈（中入出右左入出–>中左右）

// 迭代法--栈
// O(n) 0ms; O(n) 10.8MB
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root == nullptr) return result;
        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;
    }
};

94# 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

img 
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
// 递归法
// O(n) 0ms; O(n) 10.71MB
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode *root, vector<int> &vec) {
        if (root == nullptr) return;
        inorder(root->left, vec);
        vec.push_back(root->val);
        inorder(root->right, vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vec;
        inorder(root, vec);
        return vec;
    }
};

// 迭代法--栈
// O(n) 0ms; O(n) 10.79MB
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode *cur = root;
        while (cur != nullptr || !st.empty()) {
            if (cur != nullptr) { // 深度遍历左子节点
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                result.push_back(cur->val);
                st.pop();
                cur = cur->right; // 访问根节点并弹出后再访问右子节点
            }
        }
        return result;
    }
};

145# 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

**输入：**root = [1,null,2,3]

输出：[3,2,1]

解释：

img

示例 2：

**输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

解释：

img

示例 3：

**输入：**root = []

输出：[]

示例 4：

**输入：**root = [1]

输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
// 递归法
// O(n) 0ms; O(n) 10.73MB
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void postorder(TreeNode *root, vector<int> &vec) {
        if (root == nullptr) return;
        postorder(root->left, vec);
        postorder(root->right, vec);
        vec.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> vec;
        postorder(root, vec);
        return vec;
    }
};

迭代法：利用前序遍历迭代法 中入出右左入出–>中左右 的方法，这里 中入出左右入出–>中右左–reverse–>左右中

// 迭代法--栈
// O(n) 0ms; O(n) 10.87MB
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root == nullptr) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode *node = st.top();
            result.push_back(node->val);
            st.pop();
            if (node->left) st.push(node->left);
            if (node->right) st.push(node->right);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

广度优先遍历

递归法

void order(TreeNode *root, vector<vector<int>> &vec, int depth) {
    if (root == nullptr) return;
    if (vec.size() == depth) vec.push_back(vector<int>());
    vec[depth].push_back(root->val);
    order(root->left, vec, depth + 1);
    order(root->right, vec, depth + 1);
}

迭代法（队列）

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    queue<TreeNode*> que;
    if (root == nullptr) return result;
    que.push(root);
    while (!que.empty()) { // 以层为单位遍历，size确定当前层需要处理的节点数
        int size = que.size();
        vector<int> vec;
        for (int i = 0; i < size; i++){
            TreeNode *cur = que.front();
            que.pop();
            vec.push_back(cur->val);
            if (cur->left) que.push(cur->left);
            if (cur->right) que.push(cur->right);
        }
        result.push_back(vec);
    }
    return result;
}

102# 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

img 
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000
// 递归法
// O(n) 0ms; O(n) 16.77MB
class Solution {
public:
    void order(TreeNode *root, vector<vector<int>> &vec, int depth) {
        if (root == nullptr) return;
        if (vec.size() == depth) vec.push_back(vector<int>());
        vec[depth].push_back(root->val);
        order(root->left, vec, depth + 1);
        order(root->right, vec, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

// 迭代法--队列
// O(n) 0ms; O(n) 16.89MB
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if (root == nullptr) return result;
        que.push(root);
        while (!que.empty()) { // 以层为单位遍历，size确定当前层需要处理的节点数
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++){
                TreeNode *cur = que.front();
                que.pop();
                vec.push_back(cur->val);
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

107# 二叉树的层序遍历 II

题目链接

层序遍历后反转

// 迭代法--队列
// O(n) 3ms; O(n) 15.70MB
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if (root == nullptr) return result;
        que.push(root);
        while (!que.empty()) {
            vector<int> vec;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode *cur = que.front(); 
                vec.push_back(cur->val);
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            result.push_back(vec);
        }
        reverse(result.begin(), result.end()); // 默认只反转第一维度的元素顺序
        return result;
    }
};

199# 二叉树的右视图

题目链接

从右侧所能看到的节点正好是层序遍历中的最后一个节点

// 层序遍历
// O(n) 3ms; O(n) 14.77MB
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if (root == nullptr) return result;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode *cur = que.front();
                if (i == size - 1) result.push_back(cur->val);
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return result;
    }
};

637# 二叉树的层平均值

题目链接

// 层序遍历
// O(n) 0ms; O(n) 23.39MB
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> que;
        if (root == nullptr) return result;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode *cur = que.front();
                que.pop();
                sum += cur->val;
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            result.push_back(sum / size);
        }
        return result;
    }
};

429# N叉树的层序遍历

题目链接

// 迭代法--队列
// O(n) 14ms; O(n) 15.7MB
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        queue<Node*> que;
        if (root == nullptr) return result;
        que.push(root);
        while (!que.empty()) {
            vector<int> vec;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                Node *cur = que.front();
                vec.push_back(cur->val);
                que.pop();
                for (Node *child : cur->children) que.push(child);
            }
            result.push_back(vec);
        }
        return result;
    }
};

515# 在每个树行中找最大值

题目链接

// 层序遍历
// O(n) 0ms; O(n) 22.41MB
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if (root == nullptr) return result;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            int max = INT_MIN;
            for (int i = 0; i < size; i++) {
                TreeNode *cur = que.front();
                max = max > cur->val ? max : cur->val;
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            result.push_back(max);
        }
        return result;
    }
};

116# 填充每个节点的下一个右侧节点指针

题目链接

// 层序遍历
// O(n) 16ms; O(n) 19.0MB
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root == nullptr) return root;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                Node *cur = que.front();
                que.pop();
                if (i == size - 1) cur->next = nullptr;
                else cur->next = que.front();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

117# 填充每个节点的下一个右侧节点指针 II

题目链接

与上题代码相同（是否为完美二叉树不影响代码逻辑）

// 层序遍历
// O(n) 7ms; O(n) 18.52MB
class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root == nullptr) return root;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                Node *cur = que.front();
                que.pop();
                if (i == size - 1) cur->next = nullptr;
                else cur->next = que.front();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

104# 二叉树的最大深度

题目链接

// 递归法
// O(n) 0ms; O(n) 18.61MB
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

// 层序遍历
// O(n) 0ms; O(n) 18.68MB
class Solution {
public:
    int maxDepth(TreeNode* root) {
        int depth = 0;
        queue<TreeNode*> que;
        if (root == nullptr) return depth;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode *cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return depth;
    }
};

111# 二叉树的最小深度

题目链接

注意：叶子节点需要左右孩子都为空

// 层序遍历
// O(n) 0ms; O(n) 143.41MB
class Solution {
public:
    int minDepth(TreeNode* root) {
        int depth = 0;
        queue<TreeNode*> que;
        if (root == nullptr) return depth;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode *cur = que.front();
                que.pop();
                if (!cur->left && !cur->right) return depth;
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return depth;
    }
};

补充知识：递归

推荐教学视频：快速掌握递归

  • 确定问题，即函数参数和返回值
  • 解决基准问题，确定终止条件
  • 拆解问题，寻找规模更小的子问题，确定单层递归逻辑

每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中

栈溢出，系统输出的异常是Segmentation fault，考虑是否是无限递归导致

汉诺塔

void hanoi(int n, char F, char A, char T) {
	if (n = 1) {
		printf("move %d from %c to %c\n", n, F, T);
		return;
	}
	
	hanoi(n-1, F, T, A);
	printf("move %d from %c to %c\n", n, F, T);
	hanoi(n-1, A, F, T);
}

本文参考 LeetCode官方题解 及 代码随想录


http://www.kler.cn/a/534185.html

相关文章：

  • [数据结构] 线性表和顺序表
  • gesp(C++六级)（13）洛谷：P11375：[GESP202412 六级] 树上游走
  • 【人工智能】通用人工智能 AGI
  • JVM监控和管理工具
  • (dpdk f-stack)-堆栈溢出-野指针-内存泄露（问题定位）
  • 数据结构-堆和PriorityQueue
  • 微服务知识——微服务架构的演进过程
  • 【完整版】DeepSeek-R1大模型学习笔记（架构、训练、Infra）
  • Mybatis之常用动态Sql语句
  • 云原生周刊：K8s引领潮流
  • Android 中APK 体积优化的几种方法
  • 【科研】 -- 医学图像处理方向，常用期刊链接
  • Python：温度转化
  • pandas习题 070：将数据库中大数据分块读取计算
  • 2.4学习
  • TCP三次握手、四次挥手过程及原理
  • swift 专题三 swift 规范一
  • 5.6 Mybatis代码生成器Mybatis Generator (MBG)实战详解
  • 在 Debian/Ubuntu 系统上，永久固定网口的IP地址
  • 基于 SpringBoot3 的 SpringSecurity6 + OAuth2 自定义框架模板
  • DeepSeek R1技术报告关键解析(8/10)：DeepSeek-R1 的“aha 时刻”，AI 自主学习的新突破
  • Linux zcat 命令使用详解
  • labview通过时间计数器来设定采集频率
  • vue2-v-if和v-for的优先级
  • Ubuntu添加硬盘踩坑日志：SMB无权限的问题
  • 【前端构建】Rollup: 下一代 JavaScript 模块打包器