【力扣刷题】94. 二叉树的中序遍历_root = [1,null,2,3]

题目：

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例：

输入：root = [1,null,2,3]
输出：[1,3,2]

输入：root = []
输出：[]

输入：root = [1]
输出：[1]

中序遍历：左中右

前序遍历：中左右

后序遍历：左右中

解题思路：

解法一：（递归法）

无论哪种前序、中序还是后序都能使用递归方法，思考清楚逻辑过程。三部曲：1，确定参数及返回对象；2，确定结束递归的条件；3，确定单层递归的逻辑。

本题是中序遍历：

参数为递归的根节点，返回整个分支树

结束递归的条件是当前分支树遍历完

逻辑：

（全局变量申请一个列表stack，用来装元素）

1，看当前节点是否为空，为空则返回stack,不为空就返回root.left。

2，再看当前root.left为不为空，不为空就递归整个root.left，为空不做操作

3，将root.val加入到stack

4, 再看当前root.right为不为空，不为空就递归整个root.right，为空不做操作

5, 最后返回stack

stack=[]
if root is None:
    return stack
else:
    if root.left:
        stack.extend(self.inorderTraversal(root.left))
    stack.append(root.val)
    if root.right:
        stack.extend(self.inorderTraversal(root.right))    
return stack

不同遍历，只需将其中逻辑顺序换一下即可。 

知识1：

1， stack.extend()可以同时装多个元素放进列表。（元素不局限于单个数字，可以是关键字对，可以是整个树，也可以某一部分树分支）

2， 树的数据结构在python中定义成TreeNode类，

        三部分分别为root.val    root.left    root.right

解法二：（迭代法）

使用栈stack装遍历的每个树节点，res列表装输出结果

以下过程循环的条件是stack或root不为空：

1，判断当前root是否为空，不为空就将当前root放进stack，然后将root.left定义为新root，（这样就会一路往左分支飞奔到底，直到不存在左分支的左分支的。。。）

2，左分支不存在了，就将当前stack栈顶节点释放传递给tem，此时就要保存当前tem.val进res，然后再将root.right定义为新root,（接着又进入右分支的左节点，直到右分支的右分支。。也没有节点了，循环结束）

res=[]
stack=[]
while(stack or root):
    if root:
        stack.append(root)
        root=root.left
    else:
        tem=stack.pop()
        res.append(tem.val)
        root=tem.right
return res