二叉树经典例题的题解
    本文将为大家详细介绍几个经典的二叉树例题，并提供对应的解题思路和代码实现。
    1. 二叉树的遍历
    二叉树的遍历是二叉树操作中最基础的操作。它分为三种遍历方式：前序遍历、中序遍历和后序遍历。其中，前序遍历是按照“根左右”顺序遍历，中序遍历是按照“左根右”顺序遍历，后序遍历是按照“左右根”顺序遍历。
    遍历的实现方式主要有两种：递归和非递归。递归实现比较简单，非递归实现可以利用栈来实现。
    以下是前序遍历的递归实现：
    void preorderTraversal(TreeNode* root) {
    if (root != nullptr) {
    cout << root->val << ' ';
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    }
    }
    以下是前序遍历的非递归实现：
    void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
    TreeNode* node = st.top();
    st.pop();
    cout << node->val << ' ';
    if (node->right != nullptr) st.push(node->right);
    if (node->left != nullptr) st.push(node->left);
    }
    }
    2. 二叉树的最大深度
    二叉树的最大深度是指从根节点到叶子节点的最长路径上的节点数。求二叉树的最大深度可以使用递归或BFS（广度优先搜索）实现。
    以下是递归实现：
    int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return 1 + max(leftDepth, rightDepth);
    }
    以下是BFS实现：
    int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    int depth = 0;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
    int size = q.size();
    depth++;
    for (int i = 0; i < size; i++) {
    TreeNode* node = q.front();
    q.pop();
    if (node->left != nullptr) q.push(node->left);
    if (node->right != nullptr) q.push(node->right);
    }
    }
    return depth;
    }
    3. 判断两个二叉树是否相同
    判断两个二叉树是否相同可以通过递归实现。具体做法是比较两个根节点的值是否相等，再分别比较左子树和右子树是否相同。
    以下是代码实现：
    bool isSameTree(TreeNode* p, TreeNode* q) {
二叉树中序遍历非递归算法    if (p == nullptr && q == nullptr) return true;
    if (p == nullptr || q == nullptr) return false;
    if (p->val != q->val) return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
    以上就是本文的二叉树经典例题的题解，希望对大家有所帮助。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。