二叉树的遍历

前序、中序、后序、层序遍历 打包，讲解很棒！

只需要改变遍历的顺序即可

前序遍历

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def helper(root):
            if not root:return 
            res.append(root.val)
            helper(root.left)
            helper(root.right)
        helper(root)
        return res

中序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res=[]
        def helper(root):
            if not root: return 
            helper(root.left)
            res.append(root.val)
            helper(root.right)
        helper(root)
        return res

后序遍历

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def helper(root):
            if not root:
                return 
            helper(root.left)
            helper(root.right)
            res.append(root.val)
        helper(root)
        return res

层序遍历

剑指 Offer 32 - I. 从上到下打印二叉树

• 队列中存储当前层的节点，然后利用先进先出特性得到结果 。构建队列： queue = collections.deque()
  • 同一层的节点，左儿子先进入，右儿子后进入 （如 queue的 2，3）
  • 对于子节点，左儿子弹出后，将左儿子的左右孙子连接到右儿子后面（如 queue的3，4，5）。右儿子弹出后，将右儿子的左右孙子继续连接到左儿子的左右孙子后面（如 queue的 4,5,6,7）

以如下二叉树为例，说明队列的先进先出，并得到层序遍历的打印结果[1,2,3,4,5,6,7]

res（存储节点的值）	queue （存储节点，因为要判断是否有左右子节点）
[]	1
[1]	2,3
[1,2]	3,4,5
[1,2,3]	4,5,6,7
[1,2,3,4]	5,6,7
[1,2,3,4,5]	6,7
[1,2,3,4,5,6]	7
[1,2,3,4,5,6,7]	空

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root: return []
        from collections import deque
        res=[]
        queue=deque()
        queue.append(root)
        while queue:
            node=queue.popleft()
            res.append(node.val)
            if node.left:queue.append(node.left)
            if node.right:queue.append(node.right)
        return res

102. 二叉树的层序遍历

上一题把所有遍历的结果保存在数组中，即[1,2,3,4,5,6,7]。该题与上题的不同之处在于，这一次把每一层的元素保存在结果中，即 [[1],[2,3],[4,5,6,7]].

所以只需要在range(len(queue)) 范围内，增加临时变量temp保存当前层的结果。

注意！即便
if node.left: queue.append(node.left)
if node.right: queue.append(node.right) 会改变queue的长度，for i in range(len(queue))在超出当时赋值range(len(queue))范围后才跳出for循环（即，i的变化范围是0|0,1|0,1,2,3|,而不会随着循环语句中queue的改变而改变for循环次数)

如：

nums=[0,1,2]
for i in range(len(nums)):
    nums.pop()
    print(i) 

结果为： 0 1 2 。不随着nums的变化而改变for循环的次数

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        res = []
        queue = collections.deque()
        queue.append(root)
        while queue:
            tmp = []
            for i in range(len(queue)):         
                node = queue.popleft()
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp)
        return res