探索二叉树的奥秘:全面解析遍历技巧与在线OJ挑战实战

发布于:2024-05-21 ⋅ 阅读:(34) ⋅ 点赞:(0)

目录

二叉树的遍历

前序遍历

中序遍历

后序遍历

层序遍历

二叉树基础OJ题

单值二叉树

检查两颗树是否相同

对称二叉树

二叉树的前序遍历

二叉树的后序遍历

二叉树中序遍历

另一颗树的子树


二叉树的遍历

        二叉树有四种主要的遍历方式:

  1. 前序遍历(Preorder Traversal):访问顺序为根节点 -> 左子树 -> 右子树。递归公式通常表示为:root, left, right

  2. 中序遍历(Inorder Traversal):访问顺序为左子树 -> 根节点 -> 右子树。递归公式为:left, root, right

  3. 后序遍历(Postorder Traversal):访问顺序为左子树 -> 右子树 -> 根节点。递归公式为:left, right, root

  4. 层序遍历(Level Order Traversal):从上到下、从左到右访问每一层的节点。这是唯一一种广度优先遍历策略,而非深度优先。

前序遍历

        二叉树的前序遍历顺序是:根 → 左子树 → 右子树,非递归遍历二叉树时,利用栈能有效模拟前序遍历(根-左-右)过程:先将所有左节点压栈并访问,随后逐个弹出栈顶节点并处理其右子树,以此循环直至栈空,完成整个树的遍历。

具体步骤如下:

  1. 将左路结点入栈,入栈的同时访问左路结点。
  2. 取出栈顶结点top。
  3. 准备访问top结点的右子树。

代码实现如下:

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> preorderTraversal(TreeNode* root)
    {
        stack<TreeNode*> st;      // 使用栈存储待访问的节点
        vector<int> ret;         // 用于存储遍历结果
        
        // 初始化当前访问节点为根节点
        TreeNode* cur = root;
        
        // 当当前节点非空或栈非空时继续遍历
        while (cur || !st.empty())
        {
            // 遍历到最左侧的节点,沿途压栈并记录节点值
            while (cur)
            {
                st.push(cur);           // 当前节点入栈
                ret.push_back(cur->val); // 记录节点值
                cur = cur->left;       // 移动到当前节点的左子节点
            }
            
            // 当左子树遍历完后,访问栈顶节点的右子树
            TreeNode* top = st.top();     // 获取栈顶节点
            st.pop();                   // 栈顶节点出栈(已访问)
            cur = top->right;           // 移动到栈顶节点的右子节点继续遍历
        }
        
        return ret; // 返回前序遍历的结果
    }
};

中序遍历

        二叉树的中序遍历顺序是:左子树 → 根 → 右子树,我们可以先将二叉树的左路结点入栈,当左路结点入栈完毕后,再从栈顶依次取出结点,在取出结点的同时便对其进行访问,此时就相当于先访问了左子树再访问了根,之后再用同样的方式访问取出结点的右子树即可。

具体步骤如下:

  1. 将左路结点入栈。
  2. 取出栈顶结点top并访问。
  3. 准备访问top结点的右子树。

代码实现如下:

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> inorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*> st; // 使用栈辅助遍历过程
        vector<int> ret; // 存储遍历结果
        
        // 初始化当前访问节点为根节点
        TreeNode* cur = root;
        
        // 当当前节点非空或栈非空时,继续遍历
        while (cur != nullptr || !st.empty())
        {
            // 1. 遍历到最左侧的节点,沿途将非空的左子节点压入栈中
            while (cur != nullptr)
            {
                st.push(cur);
                cur = cur->left; // 移动到当前节点的左子节点
            }
            
            // 2. 取出栈顶节点(当前节点的左子树已经遍历完成),访问该节点,并将其值存入结果vector
            TreeNode* top = st.top();
            st.pop();
            ret.push_back(top->val);
            
            // 3. 准备访问当前节点的右子树
            cur = top->right; // 移动到当前节点的右子节点
        }
        
        return ret; // 完成遍历后,返回中序遍历的结果vector
    }
};

后序遍历

        二叉树的后序遍历顺序是:左子树 → 右子树 → 根,我们可以先将二叉树的左路结点入栈,当左路结点入栈完毕后,再观察栈顶结点,若栈顶结点的右子树为空,或栈顶结点的右子树已经被访问过了,则栈顶结点可以出栈并访问,若栈顶结点的右子树还未被访问,则用同样的方式访问栈顶结点的右子树,直到其右子树被访问后再访问该结点,这时的访问顺序遵循了二叉树的后序遍历所要求的顺序。

具体步骤如下:

  1. 将左路结点入栈。
  2. 观察栈顶结点top。
  3. 若top结点的右子树为空,或top结点的右子树已经访问过了,则访问top结点。访问top结点后将其从栈中弹出,并更新上一次访问的结点为top。
  4. 若top结点的右子树还未被访问,则准备访问其右子树。

代码实现如下:

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> postorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*> st; // 辅助栈,用来存储待访问的节点
        vector<int> ret; // 用于存放后序遍历的结果
        TreeNode* cur = root; // 当前访问的节点,初始化为根节点
        TreeNode* prev = nullptr; // 上一个访问过的节点,初始为nullptr

        // 当当前节点非空或栈非空时,继续遍历
        while (cur != nullptr || !st.empty()) 
        {
            // 1. 一直向左走到尽头,将路径上的节点压入栈中
            while (cur != nullptr) 
            {
                st.push(cur);
                cur = cur->left;
            }

            // 2. 取出栈顶节点
            TreeNode* top = st.top();

            // 3. 如果当前节点的右子树为空,或者右子树已经被访问过了(由prev标记)
            // 则可以访问当前节点,然后将其从栈中弹出,转向下一个节点(即其父节点)
            if (top->right == nullptr || top->right == prev) 
            {
                st.pop(); // 弹出当前节点
                ret.push_back(top->val); // 访问当前节点
                prev = top; // 更新上一个访问的节点为当前节点
                cur = nullptr; // 重置cur,以便下一轮循环从栈顶获取新节点
            }
            else 
            { // 4. 如果右子树还没访问,则转向右子树
                cur = top->right;
            }
        }

        return ret; // 完成遍历后,返回后序遍历的结果vector
    }
};

层序遍历

        二叉树的层序遍历顺序是按照从上至下、从左至右的层次顺序访问每个节点。实现层序遍历的迭代方法主要依赖于队列(queue)数据结构。

具体步骤如下:

  1. 初始化: 创建一个空队列,并将二叉树的根节点(如果非空)放入队列中。同时,创建一个容器(如vector)用于存储遍历结果的每一层节点值。

  2. 循环处理: 当队列非空时,执行以下操作:

    • 出队: 从队列中取出一个节点(称为当前节点),并将它的值添加到结果容器的当前层节点值列表中。
    • 入队子节点: 将当前节点的左右子节点(如果存在)依次放入队列中。注意保持先左后右的顺序,以维持层次遍历的顺序。
    • 结束当前层: 当当前层的所有节点都已被处理(即当前层的节点都已出队且它们的子节点已入队),则在结果容器中开始新的一层节点值列表。
  3. 重复步骤2:直到队列变空。每次完成一层的处理,实际上是在结果容器中增加了一个新的子vector,其中包含了该层所有节点的值。

代码实现如下:

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>> ret; // 最终返回的结果,存储每层节点的值
        if (root == nullptr) return ret; // 空树情况,直接返回空结果

        queue<TreeNode*> q; // 辅助队列,用来存储每一层的节点
        q.push(root); // 将根节点入队

        while (!q.empty()) 
        {
            int levelSize = q.size(); // 当前层的节点数量
            vector<int> levelNodes; // 用于存储当前层节点的值

            // 遍历当前层的每一个节点
            for (int i = 0; i < levelSize; ++i) 
            {
                TreeNode* node = q.front(); // 取出队首节点
                q.pop(); // 队首节点出队

                levelNodes.push_back(node->val); // 记录节点值

                // 将当前节点的左右子节点(如果存在)加入队列,以便下一层的遍历
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            // 当前层遍历完成后,将当前层的节点值加入最终结果
            ret.push_back(levelNodes);
        }

        return ret; // 完成所有层的遍历后,返回结果
    }
};

二叉树基础OJ题

单值二叉树-来源

题目描述:

        如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。

        只有给定的树是单值二叉树时,才返回 true;否则返回 false

示例:

代码:

class Solution 
{
public:
    // 定义一个公共成员函数isUnivalTree,接受一个指向二叉树根节点的指针作为参数
    bool isUnivalTree(TreeNode* root) 
    {
        // 如果根节点为空,认为它是单值树(空树可以视为所有节点值相同的一种特殊情况)
        if(root == nullptr)
        {
            return true;
        }
        
        // 检查左子树:如果存在左子节点且其值不等于根节点的值,则返回false,表示不是单值树
        if( root->left && root->left->val != root->val)
        {
            return false;
        }
        
        // 检查右子树:如果存在右子节点且其值不等于根节点的值,则返回false,表示不是单值树
        if( root->right && root->right->val != root->val)
        {
            return false;
        }

        // 递归检查左子树和右子树是否也都是单值树。只有当左右子树都是单值树且它们的值与根节点相同,整棵树才是单值树。
        return isUnivalTree(root->left) && isUnivalTree(root->right);
    }
};

检查两颗树是否相同-来源

题目描述:

        给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。

        如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例:

 

代码:

class Solution 
{
public:
    // 定义一个公共成员函数isSameTree,接受两个指向二叉树根节点的指针作为参数
    bool isSameTree(TreeNode* p, TreeNode* q) 
    {
        // 如果p和q都为nullptr,表示两个子树都是空树,因此它们相同
        if (p == nullptr && q == nullptr) 
        {
            return true;
        } 
        
        // 如果只有一个为空,另一个非空,说明两棵树结构不同
        else if (p == nullptr || q == nullptr) 
        {
            return false;
        } 
        
        // 如果当前节点的值不同,两棵树也不相同
        else if (p->val != q->val) 
        {
            return false;
        } 
        
        // 如果以上情况都不满足,继续递归比较左右子树
        else 
        {
            // 同时递归检查左子树和右子树是否相同
            // 只有当左右子树均相同,整个树才相同
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    }
};

对称二叉树-来源

题目描述:

        给你一个二叉树的根节点 root , 检查它是否轴对称。

示例:

代码:

class Solution 
{
public:
    // 辅助函数check,用于递归地比较二叉树的对称性
    // 接受两个TreeNode指针,分别代表原树中的两个节点(用于比较)
    bool check(TreeNode *p, TreeNode *q) 
    {
        // 如果p和q都为nullptr,表示当前层的左右节点都已检查过且匹配,继续向上返回true
        if (!p && !q) 
            return true;
        
        // 如果p和q中只有一个为nullptr,说明左右子树节点数量不对称,返回false
        if (!p || !q) 
            return false;
        
        // 检查当前节点值是否相等,并递归检查“左子树的左节点”与“右子树的右节点”,
        // 以及“左子树的右节点”与“右子树的左节点”是否对称
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    // 主函数isSymmetric,接收二叉树的根节点,调用check函数来判断整棵树是否对称
    // 传入根节点两次作为check的参数,初始时比较的是根节点的左子树和右子树
    bool isSymmetric(TreeNode* root) 
    {
        return check(root, root);
    }
};

二叉树的前序遍历-来源

题目描述:

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

示例:

代码:

class Solution 
{
public:
    // 前序遍历的辅助函数,采用递归方式实现
    // 参数root为当前访问的节点,res为存储遍历结果的向量
    void preorder(TreeNode *root, vector<int> &res) 
    {
        // 如果当前节点为空,则直接返回,结束本次递归
        if (root == nullptr) 
        {
            return;
        }
        
        // 遍历顺序:先访问当前节点,将其值存入结果向量res
        res.push_back(root->val);
        
        // 递归遍历左子树
        preorder(root->left, res);
        
        // 递归遍历右子树
        preorder(root->right, res);
    }

    // 主函数,用于执行二叉树的前序遍历并返回遍历结果
    // 创建一个空向量res,调用preorder函数开始遍历
    vector<int> preorderTraversal(TreeNode *root) 
    {
        vector<int> res;
        preorder(root, res);
        return res; // 返回存储了前序遍历结果的向量
    }
};

二叉树的中序遍历-来源

题目描述:

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

示例:

代码:

class Solution 
{
public:
    // 中序遍历的辅助函数,采用递归方式实现
    // 参数root为当前访问的节点,res为存储遍历结果的向量
    void inorder(TreeNode* root, vector<int>& res) 
    {
        // 如果当前节点为空,则直接返回,结束本次递归
        if (!root) 
        {
            return;
        }
        
        // 递归遍历左子树
        inorder(root->left, res);
        
        // 遍历顺序:访问当前节点,将其值添加到结果向量res中
        res.push_back(root->val);
        
        // 递归遍历右子树
        inorder(root->right, res);
    }

    // 主函数,执行二叉树的中序遍历并返回遍历结果
    // 初始化一个空向量res,调用inorder函数开始遍历
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        inorder(root, res);
        return res; // 返回存储了中序遍历结果的向量
    }
};

二叉树的后序遍历-来源

题目描述:

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

示例:

代码:

class Solution 
{
public:
    // 后序遍历的辅助函数,采用递归方式实现
    // 参数root为当前访问的节点,res为存储遍历结果的向量
    void postorder(TreeNode *root, vector<int> &res) 
    {
        // 如果当前节点为空,则直接返回,结束本次递归
        if (root == nullptr) 
        {
            return;
        }
        
        // 递归遍历左子树
        postorder(root->left, res);
        
        // 递归遍历右子树
        postorder(root->right, res);
        
        // 遍历顺序:先遍历左右子树,最后访问当前节点,并将其值添加到结果向量res中
        res.push_back(root->val);
    }

    // 主函数,执行二叉树的后序遍历并返回遍历结果
    // 初始化一个空向量res,调用postorder函数开始遍历
    vector<int> postorderTraversal(TreeNode *root) 
    {
        vector<int> res;
        postorder(root, res);
        return res; // 返回存储了后序遍历结果的向量
    }
};

另一颗树的子树-来源

题目描述:

        给你两棵二叉树 rootsubRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false

        二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例:

代码:

class Solution 
{
public:
    // 辅助函数check,用于比较两棵树的结构及节点值是否完全相同
    // o和t分别是待比较的两个树的根节点
    bool check(TreeNode *o, TreeNode *t) 
    {
        // 如果o和t都为空,说明当前子树比较完毕且相同,返回true
        if (!o && !t) 
        {
            return true;
        }
        // 如果o和t其中一个为空,或者它们的值不同,说明不相同,返回false
        if ((o && !t) || (!o && t) || (o->val != t->val)) 
        {
            return false;
        }
        // 递归比较左右子树
        return check(o->left, t->left) && check(o->right, t->right);
    }

    // 深度优先搜索辅助函数dfs,用于在树s中查找是否存在和树t相同的子树
    // o是树s中的当前节点,t是待查找的子树的根节点
    bool dfs(TreeNode *o, TreeNode *t) 
    {
        // 如果当前节点o为空,说明没有找到匹配的子树,返回false
        if (!o) 
        {
            return false;
        }
        // 检查当前节点o为根的子树是否与t相同,或在其左子树、右子树中寻找
        return check(o, t) || dfs(o->left, t) || dfs(o->right, t);
    }

    // 主函数isSubtree,接收两棵树的根节点s和t,判断s中是否包含t作为子树
    // 直接调用dfs函数进行深度优先搜索
    bool isSubtree(TreeNode *s, TreeNode *t) 
    {
        return dfs(s, t);
    }
};

网站公告

今日签到

点亮在社区的每一天
去签到