大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
二叉树的遍历是数据结构中非常基础的内容了,今天这一篇文章我们来详细了解一下二叉树的前序遍历,二叉树的前序遍历顺序是根节点-左子树-右子树,本文对递归和栈模拟的方法都有实现
一、递归方法
递归方法可以说是很简了,我们秉承先去往左节点再去往右节点的原则就好了
// assume that we have TreeNode, and res is to store the answer
void preorder(TreeNode *root, vector<int> &res) {
if (root == nullptr) {
return;
}
res.push_back(root->val); // we will record every node we have traveled
preorder(root->left, res); // to left first
preorder(root->right, res); // to right
}
//main
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
preorder(root, res);
return res;
}
二、栈实现
我们使用栈迭代来模拟递归的过程,事实上,递归的过程隐式地维护了一个栈,(递归储存了状态,当return 的时候相当于状态集合的.pop() )
具体地:我们将我们从根节点开始遍历到的每一个值都放入我们的答案数组,将遇到的每一个节点都放入节点数组,当节点往一个方向遍历到底(node == NULL) 的时候,我们就要pop这个栈,回到上一层,就像递归的 return 一样
记住:遍历完左边再往右边走,这也是代码中第二个while 的意义
vector<int> preorderTravel (TreeNode root) {
vector<int> res ; // store the answer
if(root == NULL) {
return ans ;
}
stack<TreeNode*> stk ; // store every node we have traveled
TreeNode *node = root ;
while(!stk.empty() || node != NULL) {
while(node != NULL) {
res.emplace_back(node -> val) ; // push_back,we should every val we met in "preorderTravel"
stk.emplace(node) ; // push
node = node -> left ; // go to left frst
}
node = stk.top() ;
stk.pop() ; // same as "return" in recursion
node = node -> right ;
}
return res ;
}
本文主要是对栈模拟实现递归的一个练习,如有不正,请指出,感激不尽
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195293.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...