二叉树的先序、中序、后序以及层次遍历

二叉树的遍历

---

先序遍历

先序遍历的实现思想是：

1. 访问根节点；
2. 访问当前节点的左子树；

3. 若当前节点无左子树，则访问当前节点的右子树；

   
   先序遍历示意.png

• 代码实现
  用python实现树的先序遍历有两种方法：递归和非递归
  递归方法： 每次递归，只需要判断结点是不是None，否则按照中左右的顺序打印出结点value值。

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

非递归方法: 非递归方法一般使用占结构来实现，由于先序遍历的顺序是中左右，所以我们每次先打印当前结点curr，并将右子结点push到栈中，然后将左子结点压入栈，再pop出左节点作为下一节点。
入栈和出栈条件：
栈不为空，一直循环；每次循环一次，则出栈一个结点；
循环结束条件：
栈空。
实现代码如下：

class Solution:
    def preorderTraversal(self, root):  ## 前序遍历
        stack = []
        sol = []
        curr = root
        while len(stack)>0 :
            sol.append(curr.val)
            if curr.right is not None:
                stack.append(curr.right)
            if curr.left is not None:
                stack.append(curr.left)
            curr = stack.pop()

        return sol

中序遍历 -左中右

递归实现
每次递归，只需要判断结点是不是None，否则按照左中右的顺序打印出结点value值。
代码实现：

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

循环实现
对于中序遍历的循环实现，每次将当前结点(curr)的左子结点push到栈中，直到当前结点(curr)为None。这时，pop出栈顶的第一个元素，设其为当前结点，并输出该结点的value值，且开始遍历该结点的右子树。

class Solution:
    def inorderTraversal(self, root):
        stack = []
        sol = []
        curr = root
        while stack or curr:
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                curr = stack.pop()
                sol.append(curr.val)
                curr = curr.right
        return sol

后序遍历 左右中

递归实现：

    def postorderTraversal(self, root):  ##后序遍历
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return [] 
        return  self.inorderTraversal(root.left) + self.inorderTraversal(root.right) + [root.val]

非递归实现

# 后序打印二叉树（非递归）
# 使用两个栈结构
# 第一个栈进栈顺序：左节点->右节点->跟节点
# 第一个栈弹出顺序： 跟节点->右节点->左节点(先序遍历栈弹出顺序：跟->左->右)
# 第二个栈存储为第一个栈的每个弹出依次进栈
# 最后第二个栈依次出栈
def postOrderTraverse(node):
    stack = [node]
    stack2 = []
    while len(stack) > 0:
        node = stack.pop()
        stack2.append(node)
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    while len(stack2) > 0:
        print(stack2.pop().val)

层次遍历

---

按照二叉树的层次从左到右依次遍历每层的节点，具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。

二叉树层次遍历.png

遍历的实现过程示意：
首先，根结点 1 入队；
根结点 1 出队，出队的同时，将左孩子 2 和右孩子 3 分别入队；
队头结点 2 出队，出队的同时，将结点 2 的左孩子 4 和右孩子 5 依次入队；
队头结点 3 出队，出队的同时，将结点 3 的左孩子 6 和右孩子 7 依次入队；
不断地循环，直至队列内为空

代码实现：参考 https://blog.csdn.net/songyunli1111/article/details/81706801

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        outList=[]
        queue=[root]
        while queue!=[] and root:
            outList.append(queue[0].val)
            if queue[0].left!=None:
                queue.append(queue[0].left)
            if queue[0].right!=None:
                queue.append(queue[0].right)
            queue.pop(0)
        return outList