題目
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?
解法思路（一）
- 借助棧；
- 借助輔助類
Command；
關(guān)于輔助類 Command
- 包裝了
TreeNode和命令c； - 命令有兩種：
go和print； -
go的話要把當(dāng)前節(jié)點(diǎn)的左右孩子入棧； -
print的話要就是遍歷到這個節(jié)點(diǎn)了，要把該節(jié)點(diǎn)放入遍歷的結(jié)果集；
關(guān)于棧的作用
- 后序遍歷是這樣的：先遍歷左子樹，再遍歷右子樹，最后遍歷根；
- 因?yàn)闂Ｓ羞@樣的特點(diǎn)：先入棧的后出棧，所以最先要遍歷的節(jié)點(diǎn)最后入棧，最后要遍歷的節(jié)點(diǎn)最先入棧；
- 棧有點(diǎn)像一個備忘錄，越后面要做的事情，越先放進(jìn)棧中，這樣只需一個個拿出棧頂?shù)氖虑樽?，就不會忘記最早要干的事情?/li>
- 于遍歷來說，之后要遍歷的節(jié)點(diǎn)因之前被放進(jìn)棧中而被記起；
解法實(shí)現(xiàn)（一）
時間復(fù)雜度
- O(n)，n為樹的節(jié)點(diǎn)個數(shù)；
空間復(fù)雜度
- O(h)，h為樹的高度，因?yàn)榍靶虮闅v屬于深度優(yōu)先遍歷，所以棧的深度最深為 h；
關(guān)鍵字
后序遍歷 非遞歸 棧 輔助類 Command
實(shí)現(xiàn)細(xì)節(jié)
package leetcode._145;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution145_1 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
private class Command {
public String c;
public TreeNode treeNode;
public Command(String c, TreeNode treeNode) {
this.c = c;
this.treeNode = treeNode;
}
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<Command> stack = new Stack<>();
Command command = new Command("go", root);
stack.push(command);
while (!stack.isEmpty()) {
command = stack.pop();
if (command.c.equals("print")) {
res.add(command.treeNode.val);
} else {
assert command.c.equals("go");
stack.push(new Command("print", command.treeNode));
if (command.treeNode.right != null) {
stack.push(new Command("go", command.treeNode.right));
}
if (command.treeNode.left != null) {
stack.push(new Command("go", command.treeNode.left));
}
}
}
return res;
}
}
