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，关键是使用两个指针pnow和pre，防止做回头路！ 2. 这个pre和pnow的关系是：pnow访问了左边，移动到右边之前，pre被赋值为pnow；当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; }};新闻热点
疑难解答
