145. Binary Tree Postorder Traversal¶
Tags: Hard Tree
Link: https://leetcode.com/problems/binary-tree-postorder-traversal/
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
Answer:
递归解法：
/**
* 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:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
postorderTraversal(root, res);
return res;
}
void postorderTraversal(TreeNode * root, vector<int> & res) {
if (!root) return;
if (root -> left) postorderTraversal(root -> left, res);
if (root -> right) postorderTraversal(root -> right, res);
res.push_back(root -> val);
}
};
使用栈的解法主要有两种：一种是使用双栈，一种是使用单栈。
先看使用单栈的方法，考虑前序遍历：根 - 左 - 右，如果交换遍历左、右的顺序，那么就变成根 - 右 - 左，最后按照访问的顺序倒序输出，所以才会使用栈的数据结构。
/**
* 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:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode *> s;
s.push(root);
while (!s.empty()) {
TreeNode *p = s.top();
s.pop();
res.push_back(p -> val);
if (p -> left) s.push(p -> left);
if (p -> right) s.push(p -> right);
}
reverse(res.begin(), res.end());
return res;
}
};
/**
* 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:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode *> s, tmp;
s.push(root);
while (!s.empty()) {
TreeNode *p = s.top();
s.pop();
tmp.push(p);
if (p -> left) s.push(p -> left);
if (p -> right) s.push(p -> right);
}
while (!tmp.empty()) {
TreeNode *p = tmp.top();
tmp.pop();
res.push_back(p -> val);
}
return res;
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Postorder Traversal.
Memory Usage: 9.2 MB, less than 83.87% of C++ online submissions for Binary Tree Postorder Traversal.
线索二叉树方法：
/**
* 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:
void reverse(TreeNode *from, TreeNode *to) {
if (from == to)
return;
TreeNode *pre = from, *cur = from -> right, *tmp;
while (true) {
tmp = cur -> right;
cur -> right = pre;
pre = cur;
cur = tmp;
if (pre == to)
break;
}
}
void printReverse(TreeNode* from, TreeNode *to, vector<int> & res) {
reverse(from, to);
TreeNode *p = to;
while (true) {
res.push_back(p -> val);
if (p == from)
break;
p = p -> right;
}
reverse(to, from);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
TreeNode dummy(0);
dummy.left = root;
TreeNode *cur = &dummy, *prev = nullptr;
while (cur) {
if (cur -> left == nullptr) {
cur = cur -> right;
}
else {
prev = cur -> left;
while (prev -> right != nullptr && prev -> right != cur)
prev = prev -> right;
if (prev -> right == nullptr) {
prev -> right = cur;
cur = cur -> left;
}
else {
printReverse(cur -> left, prev, res); // call print
prev -> right = nullptr;
cur = cur -> right;
}
}
}
return res;
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Postorder Traversal.
Memory Usage: 8.9 MB, less than 100.00% of C++ online submissions for Binary Tree Postorder Traversal.
后续遍历需要建立一个临时节点dummy，令其左孩子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。
步骤：
当前节点设置为临时节点dummy。
-
如果当前节点的左孩子为空，则将其右孩子作为当前节点。
-
如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。**倒序输出从当前节点的左孩子到该前驱节点这条路径上的所有节点。**当前节点更新为当前节点的右孩子。
-
重复以上1、2直到当前节点为空。