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
解題思路:
二叉樹的前序遍歷。題目要求用非遞歸的方法解答。那我們先看一下遞歸方法的解法。
1、遞歸解法。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vectorpreorderTraversal(TreeNode* root) { vector result; preorderHelper(result, root); return result; } void preorderHelper(vector & result, TreeNode* root){ if(root==NULL){ return; } result.push_back(root->val); preorderHelper(result, root->left); preorderHelper(result, root->right); } };
我們可以用兩個數據結構來存儲中間狀態。用隊列來存儲左孩子,用棧來存儲右孩子。優先遍歷所有左孩子。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vectorpreorderTraversal(TreeNode* root) { vector result; queue l; stack r; if(root!=NULL){ l.push(root); } while(!l.empty()||!r.empty()){ TreeNode* node = NULL; if(!l.empty()){ node=l.front(); l.pop(); }else{ node=r.top(); r.pop(); } result.push_back(node->val); if(node->left!=NULL){ l.push(node->left); } if(node->right!=NULL){ r.push(node->right); } } return result; } };