国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > 综合技术 > LeetCode Binary Tree Preorder Traversal

LeetCode Binary Tree Preorder Traversal

来源:程序员人生   发布时间:2015-04-01 08:17:23 阅读次数:2339次

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


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生