总结树的遍历（致傻b的我）

树的前序(preorder)遍历：
iterative：
用stack，依次放右节点，左节点
python代码：

class Solution:
    """
    @param root: A Tree
    @return: Preorder in ArrayList which contains node values.
    """
    def preorderTraversal(self, root):
        # write your code here
        res = []
        stack = []
        if not root:
            return res
        stack.append(root)
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

recursive:
就很简单啦，res添加当前节点，dfs访问左节点，dfs访问右节点。

class Solution:
    """
    @param root: A Tree
    @return: Preorder in ArrayList which contains node values.
    """
    def preorderTraversal(self, root):
        # write your code here
        res = []
        self.dfs(root, res)
        return res
    def dfs(self, node, res):
        if node:
            res.append(node.val)
            self.dfs(node.left, res)
            self.dfs(node.right, res)
        return

树的中序遍历(inorder): 左根右
iterative:
同样是用stack，从根开始依次把左边节点往栈里推，直到节点为空，栈pop，放入result list中，再把当前节点设置为pop出的节点的右节点，再执行上述操作。最后直到栈为空

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: A Tree
    @return: Inorder in ArrayList which contains node values.
    """
    def inorderTraversal(self, root):
        # write your code here
        stack = []
        res = []
        if not root:
            return []
        
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            res.append(node.val)
            cur = node.right
        return res

recursive:

class Solution:
    """
    @param root: A Tree
    @return: Inorder in ArrayList which contains node values.
    """
    def inorderTraversal(self, root):
        # write your code here
        res = []
        self.dfs(root, res)
        return res
        
    def dfs(self, node, res):
        if node:
            self.dfs(node.left, res)
            res.append(node.val)
            self.dfs(node.right, res)

树的后序遍历(post order):
iterative:

class Solution:
    """
    @param root: A Tree
    @return: Postorder in ArrayList which contains node values.
    """
    def postorderTraversal(self, root):
        # write your code here
        res = []
        stack = []
        if not root:
            return res
        stack.append(root)
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        res.reverse()
        return res