二叉树的前序遍历-力扣

• 二叉树的前序遍历，指先遍历中间节点，然后遍历左节点，然后遍历右节点，按照这个顺序进行递归即可。

/*** 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>& vec){if(cur == nullptr){return;}vec.push_back(cur->val);traversal(cur->left, vec);traversal(cur->right, vec);}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

• 二叉树的前序遍历，使用迭代的方法，首先将根节点入栈，然后出栈，然后将右节点入栈，左节点入栈， 这样能够确保出栈的顺序是 左节点，右节点。

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

注，在写完看代码随想录时，发现他在while循环处的条件只有 !st.empty(), 原因是它在前面将root入栈时，首先对root是否为空进行了判断，所以在循环处无需在进行判断。