二叉树的前中后层序遍历（python）

算是总结一下LeetCode这类题的模板。
讲道理我应该在一年以前写这个的（。

简明易懂遍历顺序：

TreeNode定义：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

前序

递归

# 根左右
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ans=[]
        def dlr(node):
            if not node:return
            ans.append(node.val)
            dlr(node.left)
            dlr(node.right)
        dlr(root)
        return ans

迭代

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = [root]
        ans = []
        while stack:
            node = stack.pop()
            ans.append(node.val)
            #先右后左，这样出栈时就是先左后右
            stack+=[i for i in [node.right,node.left] if i]
        return ans

中序

递归

# 左根右
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans=[]
        def ldr(node):
            if not node:return
            ldr(node.left)
            ans.append(node.val)
            ldr(node.right)
        ldr(root)
        return ans

迭代

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack=[]
        node=root
        ans=[]
        while stack or node:
            while node:
                stack.append(node)
                node=node.left
            #从最左下角的结点向上
            node=stack.pop()
            ans.append(node.val)
            node=node.right
        return ans

后序

递归

# 左右根
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        ans=[]
        def lrd(node):
            if not node:return
            lrd(node.left)
            lrd(node.right)
            ans.append(node.val)
        lrd(root)
        return ans

迭代

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = [root]
        ans = []
        while stack:
            node = stack.pop()
            ans.append(node.val)
            stack+=[i for i in [node.left,node.right] if i]
        return ans[::-1]# 把根右左倒序，变成左右根

层序

递归

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        def helper(node, depth):
            if not node: return 
            if len(ans) == depth:
                ans.append([])
            ans[depth].append(node.val)
            helper(node.left, depth + 1)
            helper(node.right, depth + 1)
        helper(root, 0)
        return ans

迭代

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        nodes=[root]
        ans=[]
        while nodes:
            ans.append([i.val for i in nodes])
            nodes=[n for i in nodes for n in [i.left,i.right] if n]
        return ans