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

目录
相关文章
|
3月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
101 1
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
50 4
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
56 16
|
1月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
2月前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
2月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
2月前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构,其中节点的度为其分支数量,树的度为树中最大节点度数。二叉树是一种特殊的树,其节点最多有两个子节点,具有多种性质,如叶子节点数与度为2的节点数之间的关系。此外,还介绍了二叉树的不同形态,包括满二叉树、完全二叉树、二叉排序树和平衡二叉树,并探讨了二叉树的顺序存储和链式存储结构。
|
2月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
2月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树:它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
26 2
|
3月前
|
C++ 容器
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
32 5