二叉树遍历

总结一下二叉树的深度遍历(DFS)和广度遍历(BFS)
首先， 创建二叉树的节点：

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

一、深度遍历

1.1 先序遍历(根->左->右)

class Solution(object):
    def preorderTraveral1(self, root):
        "递归法"
        q = []
        def recur(root):
            if root is None:
                return None
            q.append(root)
            recur(root.left)
            recur(root.right)
        recur(root)

        return q
    def  preorderTraveral2(self, root):
        """
        迭代法：利用两个stack来储存节点。
        当遍历开始时，将二叉树左节点的元素依次放入output中，
        同时用stack储存每一个节点的右节点。当左边节点遍历完
        之后，从stack中依次取出右节点，放入output中，直到stack
        中没有节点，遍历结束。
        """
        if root is None:
            return []
        stack = []
        output = []
        cur = root
        while stack or cur:
            if cur:
                output.append(root.var)
                stack.append(root.right)
                cur = cur.left
            else:
                cur = stack.pop()
        return output

1.2 中序遍历(左->根->右)

class Solution(object):
    def inorderTraveral1(self, root):
        "递归法"
        q = []
        def recur(root):
            if root == None:
                return None
            recur(root.left)
            q.append(root.val)
            recur(root.right)
        recur(root)

        return q

    def  inorderTraveral2(self, root):
        """
        迭代法：利用两个stack来储存节点。
        遍历开始时， 将左节点依次放入stack中暂时存储，
        当左节点为空时，从stack中取出一个节点放入output
        中， 然后检查当前节点的右节点，右节点不为空， 
        将其放入output中，否则继续从stack中取出节点，然
        后循环遍历，一直到stack中没有节点为止，循环结束
        """
        if root is None:
            return []
        stack = []
        output = []
        cur = root
        while cur or stack:
            if cur:
                stack.append(root)
                cur = cur.left
            else:
                cur = stack.pop()
                output.append(cur.var)
                cur = cur.right
        return output

1.3 后序遍历(左->右->根)

class Solution(object):
    def portorderTraveral1(self, root):
        "递归法"
        q = []
        def recur(root):
            if root == None:
                return None
            recur(root.left)
            recur(root.right)
            q.append(root.var)
        recur(root)

        return q

    def  postorderTraveral2(self, root):
        """
        迭代法：利用两个stack来储存节点。
        后序遍历：左/右/根，反过来是：根/右/左， 这跟先序遍历类似
        """
        if root is None:
            return []
        stack = []
        output = []
        cur = root
        while stack or cur:
            if cur:
                output.append(cur.var)
                stack.append(cur.left)
                cur = cur.right
            else:
                stack.pop()
        return output[::-1]

二、广度遍历

class Solution(object):
    def breadthTraveral(self, root):
        """
        迭代法
        利用队列实现二叉树的层次遍历
        """
        if root is None:
            return []
        q = []
        output = []
        q.append(root)
        while q:
            cur = q.pop(0)
            output.append(cur.var)
            if cur.left != None:
                q.append(cur.left)
            if cur.right != None:
                q.append(cur.right)
        return output

三、二叉树遍历进阶

Leetcode105. 从前序与中序遍历序列构造二叉树

思路：

1. 采用递归方法
2. 终止条件：子节点的左右节点为空，即preorder 或 inorder的长度为0
3. 利用preorder找根节点
4. 找到根节点之后，在inorder中对根节点定位，从而分离出左右子树
5. 不断递归，最后遍历出二叉树
   代码：

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

class Solution:
    def buildTree(self, preorder, inorder):
        if len(preorder) == None:
            return None
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])

        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        return root

Leetcode106. 从中序与后序遍历序列构造二叉树

思路：

1. 与105类似，只不过把preorder换成postorder， 利用postorder 来找根节点, 即index[-1]是二叉树的根节点

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

class Solution:
    def buildTree(self, inorder, postorder):
        if len(inorder) == 0:
            return None

        root = TreeNode(postorder[-1]) #构造根节点
        mid = inorder.index(postorder[-1])

        root.left = self.buildTree(inorder[:mid], postorder[:mid])
        root.right = self.buildTree(inorder[mid+1:], postorder[mid:-1])

        return root