二叉树的前序遍历(非递归)

二叉树的前序遍历

题目描述 :

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

 示例:

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

输出: [1,2,3]

来源：力扣（LeetCode）
OJ链接

相关:
二叉树的中序遍历(非递归)
二叉树的后序遍历(非递归)
二叉树的层序遍历(非递归)

分析: 

非递归前序遍历只需要将右孩子入栈, 遍历根节点和左孩子, 再将右孩子出栈, 从而实现 根->左->右的前序遍历, 上代码:

 

class Solution {
     vector<int> res;
public:
    vector<int> preorderTraversal(TreeNode* root) {
       stack<TreeNode*> s;
       do{
           if (!s.empty()) {
               root = s.top();
               s.pop();
           }
           while(root) {
               res.push_back(root->val);
               if (root->right) s.push(root->right);
               root = root->left;
           }
       } while (!s.empty());
       return res;
    }
};