从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容器

目录
相关文章
|
29天前
|
安全 编译器 C语言
C++入门1——从C语言到C++的过渡
C++入门1——从C语言到C++的过渡
45 2
|
1月前
|
C语言 C++
C 语言的关键字 static 和 C++ 的关键字 static 有什么区别
在C语言中,`static`关键字主要用于变量声明,使得该变量的作用域被限制在其被声明的函数内部,且在整个程序运行期间保留其值。而在C++中,除了继承了C的特性外,`static`还可以用于类成员,使该成员被所有类实例共享,同时在类外进行初始化。这使得C++中的`static`具有更广泛的应用场景,不仅限于控制变量的作用域和生存期。
45 10
|
2月前
|
算法 机器人 C语言
ROS仿真支持C++和C语言
ROS仿真支持C++和C语言
56 1
|
29天前
|
C语言 C++
实现两个变量值的互换[C语言和C++的区别]
实现两个变量值的互换[C语言和C++的区别]
16 0
|
22天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
30 3
|
C语言
C语言OJ项目参考(1039) 小球自由下落
(1039) 小球自由下落 Description 一球从M米高度自由下落,每次落地后返回原高度的一半,再落下。它在第N次落地时反弹多高?共经过多少米?保留两位小数 Input M N Output 它在第N次落地时反弹多高?共经过多少米?保留两位小数,空格隔开,放在一行 Sample Input 1000 5 Sample Output 31.25 2875.00
1433 0
|
13天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
30 10
|
6天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。
|
12天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
35 7
|
12天前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念,包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`,通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响,强调了static如何改变变量的生命周期和作用域,以及函数的可见性。
24 4