LeetCode-94-二叉树的中序遍历

原题链接
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

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

image.png

解题思路：

1. 递归和迭代，递归略；
2. 迭代思路：利用栈存储根节点，一直向左节点方向遍历，直至左节点为None，此时跳出内循环，从栈中弹出叶子节点，把该节点看作一个根节点的话，该根节点没有左节点，只需存储该节点的val，并使指针向该节点的右节点开始遍历。

Python3代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # 左-根-右
        # 递归
        if not root: return None
        ans = []
        if root.left:
            ans += self.inorderTraversal(root.left)
        ans += [root.val]
        if root.right:
            ans += self.inorderTraversal(root.right)
        return ans

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # 左-根-右
        # 迭代
        stack = []
        node = root
        res = []
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right 
        return res