一、二叉树遍历
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
