给定一个二叉树，返回它的前序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
思路：
递归很简单，这里用迭代法，使用栈模拟计算机中的指令执行情况。
1. 先创建一个Command类，存储一个字符串和一个树节点，其中字符串表示什么命令，“go”代表跳转到某个节点，“print”表示打印输出；
2. 由于是先序遍历，所以跳转到某个节点时先从栈顶弹出一条命令执行；
3. 如果弹出的命令是“print”则append进结果，如果是go命令则先向栈中压入“go” Command中存储的节点的右子节点命令，再压入“go” Command中存储的节点的左子节点命令，最后压入“print” Command中存储的节点的命令；
4. 最终返回结果数据即可
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Command(object): def __init__(self, s, node): self.s = s self.node = node class Solution(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root == None: return [] stack = [] result = [] stack.append( Command("go", root) ) while len(stack)!= 0: command = stack.pop() if command.s == "print": result.append(command.node.val) else: if command.s == "go" and command.node.right: stack.append( Command("go", command.node.right) ) if command.s == "go" and command.node.left: stack.append( Command("go", command.node.left) ) stack.append( Command("print", command.node) ) return result
对于第94题的中序遍历，只需改变入栈顺序即可
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Command(object): def __init__(self, s, node): self.s = s self.node = node class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root == None: return [] stack = [] result = [] stack.append( Command("go", root) ) while len(stack)!= 0: command = stack.pop() if command.s == "print": result.append(command.node.val) else: if command.s == "go" and command.node.right: stack.append( Command("go", command.node.right) ) stack.append( Command("print", command.node) ) if command.s == "go" and command.node.left: stack.append( Command("go", command.node.left) ) return result
对于第145题的后序遍历，只需改变入栈顺序即可
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Command(object): def __init__(self, s, node): self.s = s self.node = node class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root == None: return [] stack = [] result = [] stack.append( Command("go", root) ) while len(stack)!= 0: command = stack.pop() if command.s == "print": result.append(command.node.val) else: stack.append( Command("print", command.node) ) if command.s == "go" and command.node.right: stack.append( Command("go", command.node.right) ) if command.s == "go" and command.node.left: stack.append( Command("go", command.node.left) ) return result
