首页 > 代码库 > Binary Tree Postorder Traversal <leetcode>
Binary Tree Postorder Traversal <leetcode>
Given a binary tree, return the postorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1 2 / 3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
思路：1、非递归遍历 2、递归遍历
非递归：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 11 struct node{12 TreeNode *root;13 bool isFirst;14 };15 16 class Solution {17 public:18 vector<int> result;19 vector<int> postorderTraversal(TreeNode *root) {20 vector<node> str;21 if(root==NULL) return result;22 TreeNode *p=root;23 while(p!=NULL||str.size()!=0)24 {25 while(p!=NULL)26 {27 node n;28 n.isFirst=true;29 n.root=p;30 str.push_back(n);31 p=p->left;32 }33 if(str.size()!=0)34 {35 node temp=str.back();36 str.pop_back();37 38 if(temp.isFirst==true)39 {40 temp.isFirst=false;41 str.push_back(temp);42 p=temp.root->right;43 }44 else45 {46 result.push_back(temp.root->val);47 p=NULL;48 }49 50 }51 }52 return result;53 }54 };
2：递归
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 11 class Solution {12 public:13 vector<int> result;14 vector<int> postorderTraversal(TreeNode *root) {15 digui(root);16 return result;17 }18 19 void digui(TreeNode *root)20 {21 if(root!=NULL)22 {23 digui(root->left);24 digui(root->right);25 result.push_back(root->val);26 }27 }28 };
Binary Tree Postorder Traversal <leetcode>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。