二叉树那些事儿|二叉树前序遍历详解算法|c++|二叉树|数据结构

二叉树的遍历是数据结构中非常基础的内容了，今天这一篇文章我们来详细了解一下二叉树的前序遍历，二叉树的前序遍历顺序是根节点-左子树-右子树，本文对递归和栈模拟的方法都有实现

一、递归方法递归方法可以说是很简了，我们秉承先去往左节点再去往右节点的原则就好了

// assume that we have TreeNode, and res is to store the answer void preorder(TreeNode *root, vector &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 preorderTraversal(TreeNode *root) { vector res; preorder(root, res); return res; }

二、栈实现我们使用栈迭代来模拟递归的过程，事实上，递归的过程隐式地维护了一个栈，（递归储存了状态，当return 的时候相当于状态集合的.pop() )
具体地：我们将我们从根节点开始遍历到的每一个值都放入我们的答案数组，将遇到的每一个节点都放入节点数组，当节点往一个方向遍历到底（node == NULL) 的时候，我们就要pop这个栈，回到上一层，就像递归的 return 一样
记住：遍历完左边再往右边走，这也是代码中第二个while 的意义

vector preorderTravel (TreeNode root) { vector res ; // store the answer if(root == NULL) { return ans ; } stack 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 ; }

本文主要是对栈模拟实现递归的一个练习，如有不正，请指出，感激不尽
【二叉树那些事儿|二叉树前序遍历详解】