从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天前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
4天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
4天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
7天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
9 1
|
8天前
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
8天前
|
C语言
C语言——oj刷题——猜数字游戏
C语言——oj刷题——猜数字游戏
|
8天前
|
编译器 C语言
C语言——oj刷题——判断闰年
C语言——oj刷题——判断闰年
|
8天前
|
C语言
C语言——oj刷题——找单身狗1
C语言——oj刷题——找单身狗1
|
8天前
|
C语言
C语言——oj刷题——找单身狗2
C语言——oj刷题——找单身狗2
13 0
|
8天前
|
算法 C语言
C语言——oj刷题——杨氏矩阵
C语言——oj刷题——杨氏矩阵