题目：
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?
链接：
题解：
二叉树后序遍历。 刚接触leetcode时也做过这道题，用了很蠢笨的方法。现在学习discuss里大神们的版本，真的进步很多。下面这个版本是基于上道题目 - 二叉树先序遍历的。由于后序遍历是left -> right -> root， 先序是root -> left -> right， 所以我们改变的只是如何插入结果到 list里，以及被压入栈的先后顺序而已。在这里，pop出的结果要插入到list前部，而且要先把左子树压入栈，其次是右子树。
Time Complexity - O(n)，Space Complexity - O(n)。
/** * 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 res = new LinkedList<>(); if(root == null) return res; Stack stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()) { TreeNode node = stack.pop(); if(node != null) { res.add(0, node.val); // insert at the front of list stack.push(node.left); // opposite push stack.push(node.right); } } return res; }}
二刷:
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 res = new LinkedList<>(); if (root == null) return res; Stack stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node != null) { res.add(0, node.val); stack.push(node.left); stack.push(node.right); } } return res; }}
Recursive:
/** * 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 res = new ArrayList<>(); postorderTraversal(res, root); return res; } private void postorderTraversal(List res, TreeNode root) { if (root == null) return; postorderTraversal(res, root.left); postorderTraversal(res, root.right); res.add(root.val); }}
三刷:
Java:
Reversed preorder traversal with LinkedList and Stack:
主要使用一个LinkedList和一个stack来辅助我们的遍历。其实顺序和pre-order并没有区别，只是把遍历过的节点值不断从链表头部插入，也就形成了我们的后续遍历。注意处理节点的左节点和右节点时，对栈先压入左节点再压入右节点，之后pop时我们就会先处理右节点。
Time Complexity - O(n)，Space Complexity - O(n)。
/** * 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 res = new LinkedList<>(); if (root == null) return res; Stack stack = new Stack<>(); TreeNode node = root; stack.push(node); while (!stack.isEmpty()) { node = stack.pop(); res.add(0, node.val); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } return res; }}
Recursive:
Time Complexity - O(n)，Space Complexity - O(n)。
/** * 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 res = new ArrayList<>(); postorderTraversal(res, root); return res; } private void postorderTraversal(List res, TreeNode root) { if (root == null) return; postorderTraversal(res, root.left); postorderTraversal(res, root.right); res.add(root.val); }}
Morris Traversal:
三刷终于学习了Morris Traversal。这里的Morris Traversal也使用的是Reversed Preorder traversal with LinkedList。也就是使用类似与Preorder traversal类似的代码，以及一个LinkedList，每次从表头插入结果。
因为Postorder和Preorder的对应关系，这里与Preorder Morris Traversal不同的就是，我们要找的不是左子树的predecessor，而是右子树中当前节点的successor，也就是当前节点右子树中最左边的元素。下面我们详述一下步骤。
- 依然先做一个root的reference - node，在node非空的情况对树进行遍历。当node.right为空的时候，我们将node.val从链表res头部插入，然后向左遍历左子树
- 假如右子树非空，则我们要找到当前节点在右子树中的succesor，简称succ，一样是两种情况:
- 首次访问succ，此时succ.left = null，我们把succ和当前node连接起来，进行succ.left = node。之后讲node.val从链表res头部插入，向右遍历node.right
- 否则，我们二次访问succ，这时succ.left = node，我们做一个还原操作，设succ.left = null，然后向左遍历node.left。因为node.val已经处理过，所以不要重复处理node.val.
Time Complexity - O(n)，Space Complexity - O(1)。
/** * 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 res = new LinkedList<>(); TreeNode node = root, succ = null; while (node != null) { if (node.right == null) { res.add(0, node.val); node = node.left; } else { succ = node.right; while (succ.left != null && succ.left != node) { succ = succ.left; } if (succ.left == null) { succ.left = node; res.add(0, node.val); node = node.right; } else { succ.left = null; node = node.left; } } } return res; }}
Reference：