首页 > 代码库 > 【Leetcode】Binary Tree Preorder Traversal
【Leetcode】Binary Tree Preorder Traversal
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?
1st （ 8 tries）
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int> preorderTraversal(TreeNode *root) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. vector<int> re; /* preorder(root,re); return re; */ /*iteratively*/ stack<TreeNode *> st; if(root == NULL) return re; re.push_back(root->val); st.push(root); TreeNode *iter = root->left; /*this is important,while condition*/ while(!st.empty() || /*this is import*/iter != NULL) { while(iter != NULL) { re.push_back(iter->val); st.push(iter); iter = iter->left; } iter = st.top(); st.pop(); iter = iter->right; } return re; } /* void preorder(TreeNode *root,vector<int> &re) { if(root == NULL) return; re.push_back(root->val); preorder(root->left,re); preorder(root->right,re); } */};
2nd （ 6 tries）
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int> ans; vector<int> preorderTraversal(TreeNode *root) { //recursive /* recursive(root); return ans; */ //iteratively stack<TreeNode *> s; if(root == NULL) return ans; TreeNode *cur = root; //first check iterative pointor is not NULL or stack is not NULL, //it imply that there is some node you can scan while( cur != NULL || !s.empty() ) { //iterative all the left node while(cur != NULL) { ans.push_back(cur->val); s.push(cur); cur = cur->left; } //if all left node scaned,goto the right child tree cur = s.top(); s.pop(); cur = cur->right; } return ans; } /* void recursive(TreeNode *root) { //step 1 if(root == NULL) return; //step 2 //step 3 ans.push_back(root->val); recursive(root->left); recursive(root->right); } */};
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int> preorderTraversal(TreeNode *root) { vector<int> ans; TreeNode *cur = NULL,*pre = NULL; cur = root; while( cur ) { if( cur->left == NULL ) { //in-order here!!! //pre-order here!!! ans.push_back(cur->val); cur = cur->right; } else { pre = cur->left; while( pre->right != NULL && pre->right != cur ) { pre = pre->right; } if( pre->right == NULL ) { pre->right = cur; //pre-order here!!! ans.push_back(cur->val); cur = cur->left; } else { pre->right = NULL; //in-order here!!! cur = cur->right; } } } return ans; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。