LeetCode 94、144、145*. 二叉树的遍历（Python）

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [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