给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
前序遍历的顺序是根-左-右
思路是：
先将根结点入栈
出栈一个元素，将右节点和左节点依次入栈
重复 2 的步骤
总结： 典型的递归数据结构，典型的用栈来简化操作的算法。
递归：
/** * 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) { vector<int>v; vector<TreeNode*>s; while(root!=NULL||!s.empty()){ while(root!=NULL){ v.push_back(root->val); s.push_back(root); root=root->left; } root=s.back()->right; s.pop_back(); } return v; } };
原文：https://www.cnblogs.com/xxxsans/p/13274335.html