程序员人生 网站导航

LeetCode Binary Tree Preorder Traversal

栏目:综合技术时间:2015-04-01 08:17:23

1.题目

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?


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;     } };
思路:先序遍历的非递归方式还比较容易写,就是广度优先或呼吸遍历。要1个队列来支持。


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; } };

思路:递归就是简单,但是速度很慢。

http://www.waitingfy.com/archives/1594


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐