C++，递归
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
vector<int> result;
if (root == NULL) {
return result;
}
if (root->left != NULL) {
vector<int> left = postorderTraversal(root->left);
result.reserve(result.size() + left.size());
result.insert(result.end(), left.begin(), left.end());
}
if (root->right != NULL) {
vector<int> right = postorderTraversal(root->right);
result.reserve(result.size() + right.size());
result.insert(result.end(), right.begin(), right.end());
}
result.push_back(root->val);
return result;
}
};
C++，递归，辅助函数
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
vector<int> result;
if (root == NULL) {
return result;
} else {
postorderCore(root, result);
}
return result;
}
void postorderCore(TreeNode *root, vector<int> &result) {
if (root == NULL) {
return;
}
if (root->left != NULL) {
postorderCore(root->left, result);
}
if (root->right != NULL) {
postorderCore(root->right, result);
}
result.push_back(root->val);
return;
}
};
C++，非递归
［一个stack］
［一个cur指针］
［一个pre指针］
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
vector<int> result;
if (root == NULL) {
return result;
} TreeNode *cur = root, *pre = NULL;
stack<TreeNode *> sta; while (cur != NULL || !sta.empty()) {
while (cur != NULL) {
sta.push(cur);
cur = cur->left;
}
cur = sta.top();
if (cur->right == NULL || cur->right == pre) {
sta.pop();
result.push_back(cur->val);
pre = cur;
cur = NULL;
} else {
cur = cur->right;
}
}
return result;
}
};