Binary Tree Postorder Traversal
最后更新于：2022-04-02 01:11:10
# Binary Tree Postorder Traversal
### Source
- leetcode: [Binary Tree Postorder Traversal | LeetCode OJ](https://leetcode.com/problems/binary-tree-postorder-traversal/)
- lintcode: [(68) Binary Tree Postorder Traversal](http://www.lintcode.com/en/problem/binary-tree-postorder-traversal/)
~~~
Given a binary tree, return the postorder traversal of its nodes' values.
Example
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Challenge
Can you do it without recursion?
~~~
### 题解1 - 递归
首先使用递归便于理解。
### Python - Divide and Conquer
~~~
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @return {integer[]}
def postorderTraversal(self, root):
if root is None:
return []
else:
return self.postorderTraversal(root.left) +\
self.postorderTraversal(root.right) + [root.val]
~~~
### C++ - Traversal
~~~
/**
* 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 postorderTraversal(TreeNode *root) {
vector result;
traverse(root, result);
return result;
}
private:
void traverse(TreeNode *root, vector &ret) {
if (root == NULL) {
return;
}
traverse(root->left, ret);
traverse(root->right, ret);
ret.push_back(root->val);
}
};
~~~
### Java - Divide and Conquer
~~~
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List postorderTraversal(TreeNode root) {
List result = new ArrayList();
if (root != null) {
List left = postorderTraversal(root.left);
result.addAll(left);
List right = postorderTraversal(root.right);
result.addAll(right);
result.add(root.val);
}
return result;
}
}
~~~
### 源码分析
递归版的太简单了，没啥好说的，注意入栈顺序。
### 复杂度分析
时间复杂度近似为 O(n)O(n)O(n).
### 题解2 - 迭代
使用递归写后序遍历那是相当的简单，我们来个不使用递归的迭代版。整体思路仍然为「左右根」，那么怎么才能知道什么时候该访问根节点呢？问题即转化为如何保证左右子节点一定先被访问到？由于入栈之后左右节点已无法区分，因此需要区分左右子节点是否被访问过(加入到最终返回结果中)。除了有左右节点的情况，根节点也可能没有任何子节点，此时也可直接将其值加入到最终返回结果中。
### Python
~~~
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @return {integer[]}
def postorderTraversal(self, root):
result = []
if root is None:
return result
s = []
# previously traversed node
prev = None
s.append(root)
while s:
curr = s[-1]
noChild = curr.left is None and curr.right is None
childVisited = (prev is not None) and \
(curr.left == prev or curr.right == prev)
if noChild or childVisited:
result.append(curr.val)
s.pop()
prev = curr
else:
if curr.right is not None:
s.append(curr.right)
if curr.left is not None:
s.append(curr.left)
return result
~~~
### C++
~~~
/**
* 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 postorderTraversal(TreeNode* root) {
vector result;
if (root == NULL) return result;
TreeNode *prev = NULL;
stack s;
s.push(root);
while (!s.empty()) {
TreeNode *curr = s.top();
bool noChild = false;
if (curr->left == NULL && curr->right == NULL) {
noChild = true;
}
bool childVisited = false;
if (prev != NULL && (curr->left == prev || curr->right == prev)) {
childVisited = true;
}
// traverse
if (noChild || childVisited) {
result.push_back(curr->val);
s.pop();
prev = curr;
} else {
if (curr->right != NULL) s.push(curr->right);
if (curr->left != NULL) s.push(curr->left);
}
}
return result;
}
};
~~~
### Java
~~~
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List postorderTraversal(TreeNode root) {
List result = new ArrayList();
if (root == null) return result;
Stack s = new Stack();
s.push(root);
TreeNode prev = null;
while (!s.empty()) {
TreeNode curr = s.peek();
boolean noChild = false;
if (curr.left == null && curr.right == null) {
noChild = true;
}
boolean childVisited = false;
if (prev != null && (curr.left == prev || curr.right == prev)) {
childVisited = true;
}
// traverse
if (noChild || childVisited) {
result.add(curr.val);
s.pop();
prev = curr;
} else {
if (curr.right != null) s.push(curr.right);
if (curr.left != null) s.push(curr.left);
}
}
return result;
}
}
~~~
### 源码分析
遍历顺序为『左右根』，判断根节点是否应该从栈中剔除有两种条件，一为无子节点，二为子节点已遍历过。判断子节点是否遍历过需要排除`prev == null` 的情况，因为 prev 初始化为 null.
**将递归写成迭代的难点在于如何在迭代中体现递归本质及边界条件的确立，可使用简单示例和纸上画出栈调用图辅助分析。**
### 复杂度分析
最坏情况下栈内存储所有节点，空间复杂度近似为 O(n)O(n)O(n), 每个节点遍历两次或以上，时间复杂度近似为 O(n)O(n)O(n).
### 题解3 - Iterative
要想得到『左右根』的后序遍历结果，我们发现只需将『根右左』的结果转置即可，而先序遍历通常为『根左右』，故改变『左右』的顺序即可，所以如此一来后序遍历的非递归实现起来就非常简单了。
### 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 postorderTraversal(TreeNode *root) {
vector result;
if (root == NULL) return result;
stack s;
s.push(root);
while (!s.empty()) {
TreeNode *node = s.top();
s.pop();
result.push_back(node->val);
// root, right, left => left, right, root
if (node->left != NULL) s.push(node->left);
if (node->right != NULL) s.push(node->right);
}
// reverse
std::reverse(result.begin(), result.end());
return result;
}
};
~~~
### Java
~~~
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in ArrayList which contains node values.
*/
public ArrayList postorderTraversal(TreeNode root) {
ArrayList result = new ArrayList();
if (root == null) return result;
Deque stack = new ArrayDeque();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
Collections.reverse(result);
return result;
}
}
~~~
### 源码分析
注意入栈的顺序和最后转置即可。
### 复杂度分析
同先序遍历。
### Reference
- [[leetcode]Binary Tree Postorder Traversal @ Python - 南郭子綦](http://www.cnblogs.com/zuoyuan/p/3720846.html) - 解释清晰
- [更简单的非递归遍历二叉树的方法](http://zisong.me/post/suan-fa/geng-jian-dan-de-bian-li-er-cha-shu-de-fang-fa) - 比较新颖和简洁的实现
';