二叉树中序遍历--递归和迭代，妙啊

这是我看到官方总结然后自己思考的点，当然肯定跟官方的图没得比，但是也有加入一些自己的想法在里面。

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

示例 1：

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

输入：root = []
输出：[]
示例 3：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归，递归的关键就在于递归是如何进行的以及在什么条件下终止递归。这里可以知道，递归的终止条件就是root已经无法在向下遍历，已经到root 的叶子节点位置。

大致内容如下

def orderindex(root):
    if root:
        orderindex(root.left)
        res.append(root.val)
        orderindex(root.right)

判断当root存在的时候进行以下的遍历与

if not root：return

等价。

然后。直接调用这个方法就好，时间复杂度应该是遍历整个二叉树的o（n）

迭代

迭代就很厉害了，因为遍历整个二叉树也是从根节点从下，需要用一个栈使得导出的为逆序，也就是左子树-根节点-右子树的方式。

为了找到最底的左叶子节点，所以需要增加到最低的位置。

所以内部循环是这样一个方式。

# 内部循环
while root:
    stack.append(root)
    root = root.left

res,stack = [], []
while root or stack:
    while root: # 内部循环，当root还存在的时候，即当前节点不为null
        stack.append(root) # 将节点压入
        root = root.left    # 向左边不断寻找
    root = stack.pop()     # 弹出上一个左叶子节点
    res.append(root.val)   # 确定当前是二叉树的最底的左叶子节点
    root = root.right     # 可以将当前的节点看成根节点，寻找是否还有右叶子节点。
return res

代码思路就是，先搜索到左子节点最低度，然后将当前节点的值加入，为了确保当前节点的右叶子节点也便利完。