144. Binary Tree Preorder Traversal

 

提交网址： 

Total Accepted: 118355 Total Submissions: 297596 Difficulty: Medium

Given a binary tree, return the preorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},

1    \     2    /   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

分析：

借助栈实现非递归先序遍历算法的方法如下：
1）将二叉树的根结点作为当前结点。

2）若当前结点非空，则先访问该结点，并将该结点进栈，再将其左孩子结点作为当前结点，重复步骤2)，直到当前结点为NULL为止。

3）若栈非空，则栈顶结点出栈，并将当前结点的右孩子结点作为当前结点。

4）重复步骤2）、3)，直到栈为空且当前结点为NULL为止。

AC代码：

#include
    
     #include
     
      #include
      
       using namespace std;struct TreeNode{	int val;	TreeNode *left, *right;	TreeNode(int x): val(x), left(NULL), right(NULL) {} };class Solution{public:	vector
       
         preorderTraversal(TreeNode *root)	{	vector
        
          res;	TreeNode *p;	stack
         
           s; p=root; while(!s.empty() || p!=NULL) { if(p!=NULL) { res.push_back(p->val); s.push(p); p=p->left; } if(p==NULL) { p=s.top(); s.pop(); p=p->right; } } return res; } };// 以下为测试部分/*int main(){ Solution sol; vector
          
            res; TreeNode *root = new TreeNode(1); root->right = new TreeNode(2); root->right->left = new TreeNode(3); res=sol.preorderTraversal(root); for(int i:res) cout<
           <<" "; // 此处为vector遍历的方法，C++11标准支持 return 0;}*/