从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下)

简介: 从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145

从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中):https://developer.aliyun.com/article/1521950

144. 二叉树的前序遍历 - 力扣(LeetCode)

难度简单

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

示例 1:


输入:root = [1,null,2,3]

输出:[1,2,3]


示例 2:

输入:root = []

输出:[]


示例 3:

输入:root = [1]

输出:[1]


示例 4:


输入:root = [1,2]

输出:[1,2]


示例 5:



输入:root = [1,null,2]

输出:[1,2]


提示:

  • 树中节点数目在范围 [0, 100]
  • -100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

/**
 * 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<int> preorderTraversal(TreeNode* root) {
 
};

解析代码:

这道题用C语言写过递归版本的,当时说了后面会用非递归写,兑现承诺了属于是:

数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)_GR C的博客-CSDN博客

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty()) // 开始访问每一颗树,最后再写退出循环的条件
        {
            while(cur) // 1.左路结点的值直接输出,结点入栈
            {
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
 
            TreeNode* top = st.top(); // 2.访问左路结点的右子树
            st.pop();
            cur = top->right; // 子问题回到循环访问右子树,非递归的精髓
        }
        return v;
    }
};

94. 二叉树的中序遍历 - 力扣(LeetCode)

难度简单

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

示例 1:


输入:root = [1,null,2,3]

输出:[1,3,2]


示例 2:

输入:root = []

输出:[]

示例 3:

输入:root = [1]

输出:[1]


提示:

  • 树中节点数目在范围 [0, 100]
  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

/**
 * 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<int> inorderTraversal(TreeNode* root) {
 
    }
};

解析代码:

上面也有其它思路,但我们上面的思路前中后序遍历的思路是互通的,只是输出时机不同

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty()) // 开始访问每一颗树
        {
            while(cur) // 1.左路结点入栈
            {
                st.push(cur);
                cur = cur->left;
            }
            // 当这个结点从栈出来,表明这个结点的左路结点已经访问了
            TreeNode* top = st.top();
            st.pop();
            v.push_back(top->val); // 2. 输出这个结点
            cur = top->right; // 子问题回到循环访问右子树,非递归的精髓
        }
        return v;
    }
};

145. 二叉树的后序遍历 - 力扣(LeetCode)

难度简单

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

示例 1:


输入:root = [1,null,2,3]

输出:[3,2,1]


示例 2:

输入:root = []

输出:[]


示例 3:

输入:root = [1]

输出:[1]


提示:

  • 树中节点的数目在范围 [0, 100]
  • -100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

/**
 * 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<int> postorderTraversal(TreeNode* root) {
 
    }
};

解析代码:

后序和前面两个有点不一样,当你左路结点访问了,这时如果你的右结点为空,

你可以输出根结点,否则要访问右结点,访问右结点之后,回到根结点,

根结点的右结点还是不为空,所以根结点的右结点访问过了的情况也要输出根结点:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while(cur || !st.empty()) // 开始访问每一颗树
        {
            while(cur) // 1.左路结点入栈
            {
                st.push(cur);
                cur = cur->left;
            }
            // 当这个结点从栈出来,表明这个结点的左路结点已经访问了
            TreeNode* top = st.top();
            if(top->right == nullptr || prev == top->right) //如果右为空或者上一个输出的结点是右
            {
                v.push_back(top->val); // 2. 输出这个结点
                prev = top; // 记录上一个输出的结点
                st.pop();
            }
            else
            {
                cur = top->right; // 子问题回到循环访问右子树,非递归的精髓
            }
        }
        return v;
    }
};

本章完。

下一部分:set和map容器

目录
相关文章
|
4月前
|
安全 编译器 C语言
C++入门1——从C语言到C++的过渡
C++入门1——从C语言到C++的过渡
91 2
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
58 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
46 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
42 10
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
47 2
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
94 5
|
3月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树,由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡,支持高效插入、删除和查找操作,时间复杂度为O(log n)。AVL树通过四种旋转操作(左旋、右旋、左-右旋、右-左旋)来恢复树的平衡状态,适用于需要频繁进行数据操作的场景。
82 2
|
3月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
141 16
|
2月前
|
算法 编译器 C语言
【C语言】C++ 和 C 的优缺点是什么?
C 和 C++ 是两种强大的编程语言,各有其优缺点。C 语言以其高效性、底层控制和简洁性广泛应用于系统编程和嵌入式系统。C++ 在 C 语言的基础上引入了面向对象编程、模板编程和丰富的标准库,使其适合开发大型、复杂的软件系统。 在选择使用 C 还是 C++ 时,开发者需要根据项目的需求、语言的特性以及团队的技术栈来做出决策。无论是 C 语言还是 C++,了解其优缺点和适用场景能够帮助开发者在实际开发中做出更明智的选择,从而更好地应对挑战,实现项目目标。
112 0
|
4月前
|
C语言 C++
C 语言的关键字 static 和 C++ 的关键字 static 有什么区别
在C语言中,`static`关键字主要用于变量声明,使得该变量的作用域被限制在其被声明的函数内部,且在整个程序运行期间保留其值。而在C++中,除了继承了C的特性外,`static`还可以用于类成员,使该成员被所有类实例共享,同时在类外进行初始化。这使得C++中的`static`具有更广泛的应用场景,不仅限于控制变量的作用域和生存期。
100 10