一、二叉树遍历

1、简介

二叉树是有限个元素的集合，该集合或者为空、或者有一个称为根节点（root）的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。
经典的方法有三种，前序遍历、中序遍历和后序遍历。另外也有按层遍历。
下面主要使用递归实现二叉树的遍历。

2、代码实现

2.1 前序遍历

思想：先访问根节点，再先序遍历左子树，然后再先序遍历右子树。总的来说是根—左—右
  上图先序遍历结果为为：A,B,D,E,C,F,G
  代码如下：

def PreOrder(self, root):
        '''前序打印'''
        if root == None:
            return 
        print(root.val, end=' ')
        self.PreOrder(root.left)
        self.PreOrder(root.right)

2.2 中序遍历

思想：先中序访问左子树，然后访问根，最后中序访问右子树。总的来说是左—根—右
  上图中序遍历结果为为：D,B,E,A,F,C,G
  代码如下：

    def InOrder(self, root):
        '''中序打印'''
        if root == None:
            return
        self.InOrder(root.left)
        print(root.val, end=' ')
        self.InOrder(root.right)

2.3 后序遍历

思想：先后序访问左子树，然后后序访问右子树，最后访问根。总的来说是左—右—根
  上图后序遍历结果为为：D,E,B,F,G,C,A
  代码如下：

    def BacOrder(self, root):
        '''后序打印'''
        if root == None:
            return
        self.BacOrder(root.left)
        self.BacOrder(root.right)
        print(root.val, end=' ')

2.4 按层遍历

思想：利用队列，依次将根，左子树，右子树存入队列，按照队列的先进先出规则来实现层次遍历。
  
  代码如下：

    def levei_queue(self, root):
        '''广度优先'''
        if root == None:
            return
        # queue队列，保存节点
        queue = []
        # res保存节点值，作为结果
        #vals = []
        queue.append(root)

        while queue:
            # 拿出队首节点
            currentNode = queue.pop(0)
            #vals.append(currentNode.val)
            print(currentNode.val, end=' ')
            if currentNode.left:
                queue.append(currentNode.left)
            if currentNode.right:
                queue.append(currentNode.right)

二、Leetcode编程练习

题目一： 98 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

思路：借用辅助函数，采用中序遍历。

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def inOrder(root):
            if not root:
                return
            inOrder(root.left)
            res.append(root)
            inOrder(root.right)
            
        res = []
        if not root:
            return True
        inOrder(root)
        for i in range(1, len(res)):
            if res[i].val <= res[i-1].val:
                return False
        return True

运行结果：

题目二：102 二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

  3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

思路：考虑用队列实现（1、root为空，则返回空表；2、队列不为空，记下此时队列中的结点个数temp，temp个结点出队列的同时，记录结点值，并把结点的左右子结点加入队列）

代码实现：

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        queue = []
        queue.append(root)
        res = []
        if root == None:
            return []
        while queue:
            templist = []
            for i in range(len(queue)):                
                temp = queue.pop(0)
                templist.append(temp.val)
                if temp.left:
                    queue.append(temp.left)
                if temp.right:
                    queue.append(temp.right)
            res.append(templist)
        return res

运行结果：

题目三：107 二叉树的层次遍历II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

思路：102题最终的返回直接逆序即可。

代码实现：

class Solution:
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        queue = []
        queue.append(root)
        res = []
        if root == None:
            return []
        while queue:
            templist = []
            for i in range(len(queue)):                
                temp = queue.pop(0)
                templist.append(temp.val)
                if temp.left:
                    queue.append(temp.left)
                if temp.right:
                    queue.append(temp.right)
            res.append(templist)
        return res[::-1]

运行结果：

参考内容：
https://www.jb51.net/article/115242.htm
https://www.cnblogs.com/lliuye/p/9143676.html
https://blog.csdn.net/qq_29631251/article/details/73498483
https://blog.csdn.net/lq_lq314/article/details/79176953
http://www.cnblogs.com/freeman818/p/7252041.html