首页 > 其他分享 >LeetCode_144_二叉树的前序遍历

LeetCode_144_二叉树的前序遍历

时间:2022-11-01 11:10:55浏览次数:50  
标签:144 right TreeNode res 前序 二叉树 NULL root left


题目描述:

给定一个二叉树,返回它的 前序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

递归的写法没什么可说的,基本功

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void preorder(TreeNode* root,vector<int> &res){
if(root==NULL)
return ;
res.push_back(root->val);
preorder(root->left,res);
preorder(root->right,res);
}

vector<int> preorderTraversal(TreeNode* root) {
if(root==NULL)
return {};
vector<int> res;
preorder(root,res);
return res;
}
};

LeetCode_144_二叉树的前序遍历_迭代


迭代算法:使用stack来实现迭代算法,完成前序遍历,右子树先入栈,然后再左子树入栈

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(root==NULL)
return {};
vector<int> res;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* now=s.top();
s.pop();
if(now->right)
s.push(now->right);
if(now->left)
s.push(now->left);
res.push_back(now->val);
}
return res;
}
};

LeetCode_144_二叉树的前序遍历_子树_02


标签:144,right,TreeNode,res,前序,二叉树,NULL,root,left
From: https://blog.51cto.com/u_15855860/5812286

相关文章

  • 剑指offer——二叉树的深度
    题目描述:输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。思路1:按照深度优先遍历,设置一个全局变量ma......
  • LeetCode_617_合并二叉树
    题目描述:给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他......
  • LeetCode_637_二叉树的层平均值
    题目描述:给定一个非空二叉树,返回一个由每层节点平均值组成的数组.示例1:输入:3/\920/\157输出:[3,14.5,11]解释:第0层的平均值是3,第1层......
  • 刷题 二叉树
    代码随想录LeetCode110. 平衡二叉树carl递归思路方法一:递归求高度、递归判断是否平衡方法二:递归求高度过程中判断是否平衡细节略LeetCode257. 二叉树的......
  • C++ 不知树系列之认识二叉树(顺序、链表存储的实现)
    1.概念什么是二叉树?顾名思义,二叉树指树中的任何一个结点(除叶结点)的子结点不能多于2个。二叉树可分为:一般二叉树。只要符合二叉树的定义便可。满二叉树。满的意......
  • 力扣 889. 根据前序和后序遍历构造二叉树
    889.根据前序和后序遍历构造二叉树给定两个整数数组,preorder 和 postorder ,其中 preorder 是一个具有 无重复 值的二叉树的前序遍历,postorder 是同一棵树的......
  • 遍历二叉树多叉树的各种方法!
    /***十分强大的遍历二叉树类*该类包含了二叉树的前中后序遍历,分别用递归、迭代、Morris实现*以及二叉树的层序遍历,多叉树的前后序遍历,递归、迭代实现,多叉树的层序遍......
  • 力扣 105. 从前序与中序遍历序列构造二叉树
    105.从前序与中序遍历序列构造二叉树给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树......
  • leetcode103-二叉树的锯齿形层序遍历
    103.二叉树的锯齿形层序遍历用两个栈来实现。先把根节点放入第一个栈。循环内部根据哪个栈为空判断新的节点放到哪个栈,确定先左还是先右。当两个栈都为空时,循环结束。......
  • leetcode102-二叉树的层序遍历
    102.二叉树的层序遍历有两种实现方法。第一种是递归,第二种是队列实现。第一种是看了别人的代码写出来的,第二种是自己写的。这道题的不能直接把遍历得到的数字直接塞进res......