转载

LeetCode Binary Tree Preorder Traversal

1.题目

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

For example:

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

return [1,2,3] .

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

2.解决方案1

class Solution {  public:   vector<int> preorderTraversal(TreeNode *root) {    vector<int> ans;    deque<TreeNode*> node_list;    if(root == NULL) return ans;    node_list.push_front(root);    while(!node_list.empty())    {     TreeNode *cur = node_list.back();     node_list.pop_back();     ans.push_back(cur -> val);     if(cur -> right != NULL) node_list.push_back(cur -> right);     if(cur -> left != NULL) node_list.push_back(cur -> left);    }    return ans;   }  };

思路：先序遍历的非递归方式还比较容易写，就是广度优先或者呼吸遍历。要一个队列来支撑。

3.解决方案2

class Solution { public:  vector<int> path;  void preorder(TreeNode *root){   if(!root)      return;   path.push_back(root->val);   //if(root->left)     preorder(root->left);   //if(root->right)     preorder(root->right);  }  vector<int> preorderTraversal(TreeNode *root) {   preorder(root);   return path;  } };

思路：递归就是简单，但是速度很慢。

正文到此结束