碎碎念：
无意中刷到中序遍历二叉树，没学过，写不出来，看了很多版本的题解，看不懂，开始google什么是二叉树以及二叉树python要怎么写，最后只是了解了一些皮毛，一知半解的感觉很难受，怀疑智商，决定慢慢多刷一些二叉树的题，之后再回过头来看，总会有不一样的感受的。
简单概念：
这一篇是我把我了解到的皮毛整理成自己的笔记加深理解用的，分享给大家 三个字母了解二叉树的三种遍历(简单概念)
解题思路：
1. 其实我没有想法，不知道怎么写，于是我去看答案了
2. 答案看完还是不懂，于是我去看答案底下关于python的前排评论
3. 我试着抄了一个，想知道怎么run，实验室的同学不小心帮我按到提交了。。。很尴尬，还好我在下面有备注作者和链接，其实还是很尴尬。。。
4. 我随便点了内存分布前排的一个答案，觉得写得很简短，但是好像找不到原作者和链接，只能看code，然后因为这位不知名贡献者写得真的很简单，虽然我不懂原理，但我知道把其中三行的顺序改变，就分别可以是先序，中序，后序遍历的答案，于是我复制下来了
leetcode实测：(对不起，连名字都不知道就直接复制了，无法直接引用他，我很抱歉)
class Solution:
def inorderTraversal(self,root):
def inorder(root, list):
if root is None:
return
inorder(root.left, list)
list.append(root.val)
inorder(root.right, list)
list = []
inorder(root, list)
return list
5. 我想在本地端试着跑一下它，于是我发现直接复制离开leetcode编译环境我连执行都无法，于是又开始google如何用python实现中序遍历二叉树，开始深度怀疑自己智商有点低了。。。
**6.**因为原来对二叉树一点都不懂，最后东拼西凑查了很多版本的code，其实他们大部分的 def 写得很清楚了，只是我不知道 input 和 output 我要如何给，小白的痛苦大概只有我这种没有什么慧根的人知道，可能是要从头写到尾给我我才看得懂吧。。。好在最后有run出来，所以想把完整的code记录下来
本地端实测：(我是不是很笨，又花了一个晚上)
1. 先自定义一棵树如下图：[1, 2, 3, 4, null, 5, null]
2. 自己动手在纸上画一画这棵树，写下你的答案
先序遍历(DLR)：[1，2，4，null，3，5，null]
中序遍历(LDR)：[4，2，null，1，5，3，null]
后序遍历(LRD)：[4，null，2，5，null，3，1]
3. 本地端跑 py 对答案
4. python 代码如下, 直接复制到 .py 玩玩看
# 定义一颗树，节点本身给值，左子树和右子树给空
class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义先序遍历
def preorderTree(root):
def preorder(root, list):
if root is None:
return
list.append(root.val) # 当前节点D
preorder(root.left, list) # 左子树L
preorder(root.right, list) # 右子树R
list = []
preorder(root, list)
return list # 先序遍历二叉树最后可以从这个list看到
# 定义中序遍历
def inorderTree(root):
def inorder(root, list):
if root is None:
return
inorder(root.left, list) # 左子树L
list.append(root.val) # 当前节点D
inorder(root.right, list) # 右子树R
list = []
inorder(root, list)
return list # 中序遍历二叉树最后可以从这个list看到
# 定义后序遍历
def postorderTree(root):
def postorder(root, list):
if root is None:
return
postorder(root.left, list) # 左子树L
postorder(root.right, list) # 右子树R
list.append(root.val) # 当前节点D
list = []
postorder(root, list)
return list # 后序遍历二叉树最后可以从这个list看到
if __name__ == "__main__":
# 新建节点
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode('null')
node6 = TreeNode(5)
node7 = TreeNode('null')
# 构建二叉树
node1.left, node1.right = node2, node3
node2.left, node2.right = node4, node5
node3.left, node3.right = node6, node7
# 指定 node1 为root节点
root = node1
# 打印
print('先序排列')
print(preorderTree(root)) # [1, 2, 4, 'null', 3, 5, 'null']
print('\n')
print('中序排列')
print(inorderTree(root)) # [4, 2, 'null', 1, 5, 3, 'null']
print('\n')
print('后序排列')
print(postorderTree(root)) # [4, 'null', 2, 5, 'null', 3, 1]
补充：
前序，中序，后续遍历二叉树leetcode题号分别是#144，#94，#145，这个版本的python code在下面，试试看
# 先序遍历
class Solution:
def preorderTraversal(self,root):
def preorder(root, list):
if root is None:
return
list.append(root.val)
preorder(root.left, list)
preorder(root.right, list)
list = []
preorder(root, list)
return list
# 中序遍历
class Solution:
def inorderTraversal(self,root):
def inorder(root, list):
if root is None:
return
inorder(root.left, list)
list.append(root.val)
inorder(root.right, list)
list = []
inorder(root, list)
return list
# 后序遍历
class Solution:
def postorderTraversal(self,root):
def postorder(root, list):
if root is None:
return
postorder(root.left, list)
postorder(root.right, list)
list.append(root.val)
list = []
postorder(root, list)
return list
#144：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
#94：
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
#145：
给定一个二叉树，返回它的 后序 遍历。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
本地端实测的code部分参考了这篇关于打印二叉树的文章：
1. python实现二叉树层序遍历（逐层打印二叉树）(如何建一棵树那段code)
还有一篇我觉得写得比较完整的文章，把递归法和堆栈法的三种遍历都讲了一遍，目测可以直接复制到本地端实测，虽然我没有用到，但觉得可以推荐给大家试试看：
2. python实现二叉树和它的七种遍历