leetcode-94

94. 二叉树的中序遍历

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

通过循环创建二叉树

## 二叉树定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(i,inputs):
    if i < len(inputs):
        return TreeNode(
            inputs[i],
            left=buildTree((i+1)*2-1,inputs),
            right=buildTree((i+1)*2,inputs)
        )

解法一（递归）

中序遍历：左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此可以用递归去实现。

class Solution:
    def inorder(self,root):
        if root is None or str(root.val) == "None":
            return
        for v in self.inorderTraversal(root.left):
            yield v
        yield root.val

        for v in self.inorderTraversal(root.right):
            yield v   
    def inorderTraversal(self, root: TreeNode):

        res = inorder(root)
        return list(res)

官方解法二（非递归）

方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。

def inorder2(self,root):
    res = []
    stack = list()

    while root != None or len(stack) != 0:
        # 迭代遍历左子树，左子树遍历后，
        while root != None:
            stack.append(root) 
            root = root.left
        
        # 弹出当前节点，既左子树的父节点
        root = stack.pop()
        res.append(root.val)
        root = root.right # 遍历右子树
    return res