首页 > 编程语言 >代码随想录算法训练营第十三天 | 144.二叉树的前序遍历、94、二叉树的中序遍历、145、二叉树的后序遍历、102.二叉树的层序遍历

代码随想录算法训练营第十三天 | 144.二叉树的前序遍历、94、二叉树的中序遍历、145、二叉树的后序遍历、102.二叉树的层序遍历

时间:2024-07-15 22:54:38浏览次数:15  
标签:遍历 TreeNode cur val res right 二叉树 第十三天 left

144.二叉树的前序遍历

题目:. - 力扣(LeetCode)

思路:有递归法和使用栈来模拟递归的迭代法。

代码:

1.递归

/**
 * 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:
void Traversal(TreeNode* cur,vector<int>& res){
    if(cur==NULL)
    return;
    res.push_back(cur->val);
    Traversal(cur->left,res);
    Traversal(cur->right,res);
 }
    vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
Traversal(root,res);
return res;
}
};

2.迭代

/**
 * 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) {
stack<TreeNode*> st;
vector<int> res;
if(root==NULL)
return res;
TreeNode* cur=root;
st.push(cur);
while(!st.empty()){
    cur=st.top();
    res.push_back(cur->val);
    st.pop();
    if(cur->right) st.push(cur->right);
    if(cur->left) st.push(cur->left);
}
return res;
    }
};

94、二叉树的中序遍历

题目:. - 力扣(LeetCode)

思路:递归,迭代

代码:

1.递归

/**
 * 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:
void Traversal(TreeNode* cur,vector<int>& res){
if(cur==NULL)
return;
Traversal(cur->left,res);
res.push_back(cur->val);
Traversal(cur->right,res);
}
    vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
Traversal(root,res);
return res;
    }
};

2.迭代

/**
 * 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) {
stack<TreeNode*> st;
vector<int> res;
if(root==NULL) return res;
TreeNode* cur=root;
st.push(cur);
cur=cur->left;
while(cur!=NULL||!st.empty()){
    if(cur!=NULL){
        st.push(cur);
        cur=cur->left;
    }
    else{
        cur=st.top();
        st.pop();
        res.push_back(cur->val);
        cur=cur->right;
    }
}
return res;
    }
};

145、二叉树的后序遍历

题目:. - 力扣(LeetCode)

思路:递归,迭代

代码:

1.递归

/**
 * 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:
void Traversal(TreeNode* cur,vector<int>& res){
    if(cur==NULL)
    return;
    Traversal(cur->left,res);
    Traversal(cur->right,res);
    res.push_back(cur->val);
}
    vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
Traversal(root,res);
return res;
    }
};

2.迭代

/**
 * 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) {
stack<TreeNode*> st;
vector<int> res;
if(root==NULL)
return res;
st.push(root);
TreeNode* node=root;
while(!st.empty()){
    node=st.top();
    st.pop();
    res.push_back(node->val);
    if(node->left) st.push(node->left);
    if(node->right) st.push(node->right);
    }
    reverse(res.begin(),res.end());
    return res;
    }
};

102.二叉树的层序遍历

题目:. - 力扣(LeetCode)

思路:队列

代码:

/**
 * 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<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if (root == NULL) return res;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> a;
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                a.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            res.push_back(a);
        }
        return res;
    }
};

标签:遍历,TreeNode,cur,val,res,right,二叉树,第十三天,left
From: https://blog.csdn.net/dtgfhfd/article/details/140451168

相关文章

  • Day11(二叉树) | 二叉树的递归遍历 二叉树的迭代遍历 二叉树的统一迭代法 二
    二叉树的递归遍历终于来到了递归!!!递归是进入动态规划的第一步,有部分的递归完全可以写成动态规划!这里可以移步到左程云的视频观看.递归的步骤:确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数,并且还要明确每次递归的返......
  • 矩阵优化 DP 以及全局平衡二叉树实现的动态 DP 学习笔记
    矩阵乘法求斐波那契数列的第\(n\)项,其中\(n\le10^{18}\),对数\(m\)取模。写出转移方程,\(f_i=f_{i-1}+f_{i-2}\),直接算是\(O(n)\)的,似乎没什么办法优化。定义大小分别为\(n\timesp\)和\(p\timesm\)的矩阵(分别为\(a\)和\(b\))相乘的结果(矩阵\(c\))是一个大小为\(......
  • 数据结构-二叉树
    引入图论中的树和现实生活中的树长得一样,只不过我们习惯于处理问题的时候把树根放到上方来考虑。这种数据结构看起来像是一个倒挂的树,因此得名。定义一个没有固定根结点的树称为无根树(unrootedtree)。无根树有几种等价的形式化定义:有n个结点,n-1条边的连通无向图无向无环......
  • 树的遍历
    幻影忍者前情提要这是一棵二叉树,现在,我们要对它进行遍历<( ̄︶ ̄)>前序遍历顺序先根节点,再左节点,再右节点实现如果树为空,返回,否则:访问根节点若根节点有左孩子,前序遍历左子树若根节点有右孩子,前序遍历右子树所以,让我们来实现一下该树的前序遍历:根节点\(1\)->左孩......
  • 「代码随想录算法训练营」第十一天 | 二叉树 part1
    二叉树的基本知识链接:https://programmercarl.com/二叉树理论基础.html要点:深度优先遍历前序遍历(递归法,迭代法)中序遍历(递归法,迭代法)后序遍历(递归法,迭代法)广度优先遍历层次遍历(迭代法)由于栈就是递归的一种实现结构,因此前中后序遍历的逻辑可以借助栈使用递归的方式......
  • java List集合转Map并遍历输出
    1.使用流转map并且遍历packagecom.demo.toMap;importjava.util.ArrayList;importjava.util.List;importjava.util.Map;importjava.util.stream.Collectors;publicclassMianDemo{publicstaticvoidmain(String[]args){List<NodeList>list=......
  • 代码随想录算法训练营第22天 |二叉树part07:235. 二叉搜索树的最近公共祖先、701.二叉
    代码随想录算法训练营第22天|二叉树part07:235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点235.二叉搜索树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/代码随想录:htt......
  • LeetCode 144. 二叉树的前序遍历
    更多题解尽在https://sugar.matrixlab.dev/algorithm每日更新。组队打卡,更多解法等你一起来参与哦!LeetCode144.二叉树的前序遍历,难度中等。classSolution{publicvoidpreorderTraversal(TreeNoderoot,List<Integer>ans){if(root==null)re......
  • Python数据容器(3)--遍历与列表生成式
    文章目录遍历直接遍历索引遍历list列表tuple元组字典遍历get()方法items()方法enumerate()函数与zip()函数enumerate()函数zip()函数列表生成式语法表现形式编写基本的列表生成式带有条件的列表生成式嵌套列表生成式字符串与列表之间的转换总结遍历:列表生成式遍......
  • 树的层次遍历
    树的层次遍历是指按层次顺序访问树中所有节点的遍历方式。具体的步骤如下:从根节点开始,将根节点入队。进行循环,直到队列为空:弹出队列中的节点,并访问该节点。将该节点的所有子节点依次入队。完成遍历。层次遍历的相关知识点:队列:层次遍历需要使用一个队列来暂存节点。每次......