My code:
import java.util.ArrayList;
import java.util.List;
/**
* 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<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null)
return result;
postorderTraversal(root, result);
return result;
}
private void postorderTraversal(TreeNode root, ArrayList<Integer> result) {
if (root.left != null)
postorderTraversal(root.left, result);
if (root.right != null)
postorderTraversal(root.right, result);
result.add(root.val);
}
}
My test result:
这道题目就是一分钟解决的题目。竟然难度是。。。hard。。。
richardo你就是一个傻逼。
这道题目难点在于。。。
非递归后序遍历树。比较复杂。
代码如下：
public List<TreeNode> postOrder(TreeNode root) {
if (root == null)
return null;
TreeNode curr = null;
TreeNode pre = null;
Stack<TreeNode> s = new Stack<TreeNode>();
ArrayList<TreeNode> result = new ArrayList<TreeNode>();
s.push(root);
while (!s.isEmpty()) {
curr = s.peek();
if ((curr.left == null && curr.right == null)
|| (pre != null && (curr.left == pre || curr.right == pre))) {
result.add(curr);
pre = s.pop();
}
else {
if (curr.right != null)
s.push(curr.right);
if (curr.left != null)
s.push(curr.left);
}
}
return result;
}
**
总结： post order tree
**
Anyway, Good luck, Richardo!
My code:
/**
* 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<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (root == null)
return ret;
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode node = root;
while (node != null) {
ret.add(node.val);
if (node.left != null)
s.push(node.left);
node = node.right;
if (node == null && !s.isEmpty()) {
node = s.pop();
}
}
Stack<Integer> ss = new Stack<Integer>();
for (int i = 0; i < ret.size(); i++)
ss.push(ret.get(i));
ret = new ArrayList<Integer>();
while (!ss.isEmpty())
ret.add(ss.pop());
return ret;
}
}
看了答案才知道，原来后序遍历的reverse，是先序遍历从右侧开始。
于是先按照先序遍历从右侧开始，遍历下，之后reverse一下就行了。
参考网页：
http://www.geeksforgeeks.org/iterative-postorder-traversal/
下面讲一下 1 stack，直接模拟post order的做法。这个会更实用。
/**
* 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<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (root == null)
return ret;
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode node = root;
TreeNode pre = null;
TreeNode curr = null;
s.push(node);
while (!s.isEmpty()) {
curr = s.peek();
if ((curr.left == null && curr.right == null)
|| (pre != null && (pre == curr.left || pre == curr.right))) {
ret.add(curr.val);
pre = curr;
s.pop();
}
else {
if (curr.right != null)
s.push(curr.right);
if (curr.left != null)
s.push(curr.left);
}
}
return ret;
}
}
从头结点开始往左侧走。然后一路上把左节点和右孩子结点往栈里面塞，做好保存。
其实这样。先插入结点。再插入右孩子结点，再插入左孩子结点。然后当前指针移动到左孩子结点。当做，根节点，继续。
那么弹出的时候，往往就是先弹出左孩子结点。然后访问右孩子结点，最后才是根节点。
当前结点，左右孩子都为空。
那么出栈，存到list
可以是左结点，也可以是右结点。
当前结点访问完了，弹出。此刻的栈顶结点，有两种情况。
（1）
就是根节点。这里又可以细分成两种情况。
（1）
说明，该根节点的右孩子结点是空的。
那么，直接访问该根节点，然后弹出。
（2）
说明已经访问完了该根节点的左孩子右孩子。那么直接访问该根节点并弹出
（2）
是根节点的右孩子结点。
那么，就开始把该右结点当做根节点，开始操作。判断其右孩子是不是空，不是的话入栈。判断其左孩子是不是空，不是的话入栈。
所以if语句有两个条件：
condition 1:
curr.left == null && curr.right == null, 那么就是一个叶子结点，直接访问。
pre != null && (pre == curr.left || pre == curr.right)
这个时候已经访问完了左右孩子，就可以开始处理根节点了。直接弹出访问。
还是比较复杂的。
参考网页：
http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
网页上写的不详细。
Anyway, Good luck, Richardo!
My code:
/**
* 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<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<Integer>();
if (root == null) {
return ret;
}
Stack<TreeNode> st = new Stack<TreeNode>();
TreeNode curr = root;
TreeNode pre = null;
st.push(curr);
while (!st.isEmpty()) {
curr = st.peek();
if ((curr.left == null && curr.right == null)
|| (pre != null && (pre == curr.left || pre == curr.right))) {
st.pop();
ret.add(curr.val);
pre = curr;
}
else {
if (curr.right != null) {
st.push(curr.right);
}
if (curr.left != null) {
st.push(curr.left);
}
}
}
return ret;
}
}
还是得看原来的代码才记得清楚。
Anyway, Good luck, Richardo! --- 09/06/2016
