首页 > 代码库 > Leetcode Binary Tree Postorder Traversal
Leetcode Binary Tree Postorder Traversal
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?
vector<int> postorderTraversal(TreeNode *root){ vector<int> res; if(root == NULL) return res; stack<TreeNode *> record; record.push(root); TreeNode *pre = NULL; while(!record.empty()){ TreeNode *node = record.top(); if((node->left == NULL && node->right == NULL)||(pre!=NULL &&(pre == node->left || pre == node->right)) ){ res.push_back(node->val); record.pop(); pre = node; }else{ if(node->right) record.push(node->right); if(node->left ) record.push(node->left); } } return res;}
另一种方法：
通过不断的交换左右孩子，然后压栈，最后弹出，即可得到结果
时间复杂度为O(h),h为树的高度，空间复杂度为O(n)
vector<int> postorderTraversa(TreeNode *root){ vector<int> res; if(root == NULL) return res; stack<TreeNode *> post_record,reverse_record; post_record.push(root); while(!post_record.empty()){ TreeNode *node = post_record.top(); reverse_record.push(node); post_record.pop(); if(node->left) post_record.push(node->left); if(node->right) post_record.push(node->right); } while(!reverse_record.empty()){ res.push_back(reverse_record.top()->val); reverse_record.pop(); } return res;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。