Given a binary tree, return the PReorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3},
1 / 2 / 3return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
s思路： 1. pre-order之前有遇到過：先根，再左，后右。recursive確實容易。iterative稍微比in-order麻煩一些，需要用stack，關(guān)鍵是使用兩個指針pnow和pre，防止做回頭路！ 2. 這個pre和pnow的關(guān)系是：pnow訪問了左邊，移動到右邊之前，pre被賦值為pnow；當(dāng)pnow訪問了右邊，移動到上層之前，pre被賦值為pnow。
//方法1:recursive: pre-orderclass Solution {public: void helper(vector<int>&res,TreeNode* root){ if(!root) return; res.push_back(root->val);//root helper(res,root->left);//left helper(res,root->right);//right } vector<int> preorderTraversal(TreeNode* root) { // vector<int> res; helper(res,root); return res; }};//方法2:iterative: pre-order;stack;pre+pnowclass Solution {public: vector<int> preorderTraversal(TreeNode* root) { // vector<int> res; stack<TreeNode*> ss; TreeNode* pnow=root,*pre=NULL; while(!ss.empty()||pnow){ while(pnow){ res.push_back(pnow->val); ss.push(pnow); pnow=pnow->left; } pnow=ss.top(); if(pnow->right&&pnow->right!=pre){ pnow=pnow->right; }else{ pre=pnow; ss.pop(); pnow=NULL; } } return res; }};新聞熱點
疑難解答
