首页 > 编程语言 >C++算法练习-day38——106.从中序和后序遍历序列构造二叉树

C++算法练习-day38——106.从中序和后序遍历序列构造二叉树

时间:2024-11-09 11:49:43浏览次数:6  
标签:遍历 TreeNode day38 后序 中序 C++ 二叉树 节点 postorder

题目来源:. - 力扣(LeetCode)

题目思路分析

题目要求根据一棵二叉树的中序遍历(inorder)和后序遍历(postorder)结果重建这棵二叉树。中序遍历的特点是左子树 -> 根节点 -> 右子树,而后序遍历的特点是左子树 -> 右子树 -> 根节点。利用这两个遍历的特点,我们可以递归地重建整棵树。

  1. 后序遍历的最后一个元素是根节点:因为后序遍历是左子树 -> 右子树 -> 根节点的顺序,所以最后一个元素一定是当前子树的根节点。
  2. 在中序遍历中找到根节点的位置:一旦确定了根节点,我们可以在中序遍历中找到这个根节点的位置,这个位置将中序遍历分为左子树和右子树两部分。
  3. 递归构建左右子树:根据中序遍历中根节点的位置,我们可以将后序遍历也分为两部分,分别对应左子树和右子树。然后递归地对这两部分进行中序和后序遍历的重建。

代码:

/**  
 * 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:  
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {  
        int n = postorder.size();  
        if (n == 0) {  
            // 如果后序遍历为空,说明子树为空  
            return nullptr;  
        }  
        // 后序遍历的最后一个元素是根节点  
        TreeNode* node = new TreeNode(postorder[n-1]);  
        if (postorder.size() == 1) {  
            // 如果后序遍历只有一个元素,说明整棵树只有一个节点  
            return node;  
        }  
        int incise;  
        // 在中序遍历中找到根节点的位置  
        for (incise = 0; incise < inorder.size(); incise++) {  
            if (inorder[incise] == postorder[n-1]) {  
                break;  
            }  
        }  
        // 根据根节点的位置,将中序遍历和后序遍历分割为左右子树  
        vector<int> leftinorder(inorder.begin(), inorder.begin() + incise);  
        vector<int> rightinorder(inorder.begin() + incise + 1, inorder.end());  
        vector<int> leftpostorder(postorder.begin(), postorder.begin() + leftinorder.size());  
        vector<int> rightpostorder(postorder.begin() + leftinorder.size(), postorder.end() - 1);  
        // 递归构建左右子树  
        node->left = buildTree(leftinorder, leftpostorder);  
        node->right = buildTree(rightinorder, rightpostorder);  
        return node;  
    }  
};

知识点摘要

  1. 二叉树遍历
    • 中序遍历:左子树 -> 根节点 -> 右子树
    • 后序遍历:左子树 -> 右子树 -> 根节点
  2. 递归
    • 递归是一种在函数内部调用自身的方法,常用于解决可以分解为相似子问题的问题。
  3. 动态数组(vector)
    • 在C++中,vector是一个可以动态调整大小的数组,提供了方便的元素访问和操作方法。

通过本题,我们学习了如何利用二叉树的中序遍历和后序遍历结果来重建二叉树。这种方法依赖于递归,通过在后序遍历中找到根节点,然后在中序遍历中分割出左右子树,再递归地对左右子树进行同样的操作。这种方法不仅锻炼了我们对二叉树遍历的理解,还加深了对递归思想的应用。在实际编程中,递归是一种强大的工具,可以帮助我们解决许多看似复杂的问题。

标签:遍历,TreeNode,day38,后序,中序,C++,二叉树,节点,postorder
From: https://blog.csdn.net/L613Z/article/details/142993728

相关文章

  • RT DETR v2 TensorRT C++ 部署详解
    RT-DETRv2TensorRTC++部署详解概述随着深度学习技术的发展,目标检测算法在各种应用场景下展现出了卓越的表现。RT-DETRv2(Real-TimeDetectionTransformerv2)作为一款高效的实时目标检测模型,其结合了Transformer架构的优势与传统卷积神经网络(CNNs)的速度,为开发者提供了在......
  • 利用 C++ 开发经典 2D (超级马里奥)平台游戏(代码可用~)
    ......
  • 【华为OD技术面试手撕真题】82、环形链表II | 手撕真题+思路参考+代码解析(C & C++ & J
    文章目录一、题目......
  • 大整数相加[C++]
    0前言当我们遇到需要处理非常大的整数的情况时,标准的数据类型如int或longlongint可能无法满足需求,因为这些类型的数值范围有限。在这种情况下,我们需要一种方法来处理超出常规数据类型范围的大整数。本文将介绍如何使用C++实现大整数相加。1大整数相加的基本原理从最低位开......
  • 7-8 数据结构实验二 二叉树的遍历
    以二叉链表作存储结构,建立一棵二叉树。输出该二叉树的先序、中序、后序遍历序列,求出该二叉树的深度,并统计其叶子结点数。二叉链表的类型描述:typedefcharElemType;typedefstructBiNode{ElemTypedata;structBiNode*lchild,*rchild;}BiNode,*BiTree;......
  • C++函数名后面有个const
    ‌函数名后面加const表示该函数是一个常成员函数,即该函数不会修改类的任何成员变量。‌在C++中,常成员函数通过在函数声明和定义后添加const关键字来标识。常成员函数不能修改类的任何成员变量,这保证了类的接口的稳定性。例如: classPoint{public:intGetX()const;//......
  • C++中的继承
    在C++中,继承的方式有三种:public、protected 和 private。它们控制了基类成员在派生类中的访问权限。以下是这三种继承方式的区别:1. public 继承基类的 public 成员在派生类中保持 public。基类的 protected 成员在派生类中保持 protected。基类的 private 成员......
  • C++中的std::shared_ptr
    std::shared_ptr 是C++11标准库中的智能指针类型,用于管理动态分配的对象。与传统指针不同,std::shared_ptr 自动管理内存,并在不再使用时自动释放对象,以避免内存泄漏。它是一种共享所有权的智能指针,即可以让多个 std::shared_ptr 指向同一个对象,并且会记录有多少个 std::shar......
  • C++中类型转换static_cast
    static_cast<type> 是C++中的一种类型转换方式,用于在编译期进行静态类型转换。与C风格的强制类型转换不同,static_cast 更加安全和明确,因为它只允许特定的类型转换,避免了潜在的错误和歧义。static_cast 的用法static_cast<type>(expression) 将 expression 转换为 typ......
  • c++--拷贝构造函数&友元函数
    目录1.拷贝构造函数是什么2.拷贝构造函数的基本格式2.1默认拷贝构造函数(浅拷贝)2.2深拷贝(DeepCopy)2.3浅拷贝(ShallowCopy)2.3浅拷贝和深拷贝总结2.友元函数1.拷贝构造函数是什么拷贝构造函数是一个特殊的构造函数,用于在创建新对象时,用已有对象的数据来初始......