題目
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
解法思路（一）
前序遍歷的非遞歸實(shí)現(xiàn)
- 借助棧；
- 借助輔助類
Command；
關(guān)于輔助類 Command
- 包裝了
TreeNode和命令腮介； - 命令有兩種：
go和print惋鹅； -
go的話要把當(dāng)前節(jié)點(diǎn)的左右孩子入棧颅围； -
print的話要就是遍歷到這個(gè)節(jié)點(diǎn)了忍燥，要把該節(jié)點(diǎn)放入遍歷的結(jié)果集砚嘴；
關(guān)于棧的作用
- 前序遍歷是這樣的：先遍歷根節(jié)點(diǎn)，再遍歷左子樹灾杰，最后遍歷右子樹；
- 因?yàn)闂Ｓ羞@樣的特點(diǎn)：先入棧的后出棧熙参，所以最先要遍歷的節(jié)點(diǎn)最后入棧艳吠，最后要遍歷的節(jié)點(diǎn)最先入棧；
- 棧有點(diǎn)像一個(gè)備忘錄孽椰，越后面要做的事情昭娩，越先放進(jìn)棧中，這樣只需一個(gè)個(gè)拿出棧頂?shù)氖虑樽鍪蜇遥筒粫?huì)忘記最早要干的事情栏渺；
- 于遍歷來說，之后要遍歷的節(jié)點(diǎn)因之前被放進(jìn)棧中而被記起膀捷；
解法實(shí)現(xiàn)（一）
時(shí)間復(fù)雜度
- O(n)迈嘹，n為樹的節(jié)點(diǎn)個(gè)數(shù)；
空間復(fù)雜度
O(h)全庸，h為樹的高度秀仲，因?yàn)榍靶虮闅v屬于深度優(yōu)先遍歷，所以棧的深度最深為 h壶笼；
關(guān)鍵字
前序遍歷 非遞歸 棧 輔助類 Command
實(shí)現(xiàn)細(xì)節(jié)
package leetcode._144;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution144_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> preorderTraversal(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 {
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));
}
stack.push(new Command("print", command.treeNode));
}
}
return res;
}
}
