我的个人微信公众号：Microstrong

微信公众号ID：MicrostrongAI

微信公众号介绍：Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容，分享在学习过程中的读书笔记！期待您的关注，欢迎一起学习交流进步！

知乎主页：https://www.zhihu.com/people/MicrostrongAI/activities

Github：https://github.com/Microstrong0305

个人博客：https://blog.csdn.net/program_developer

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3
Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

解题思路：

（1） 递归解法

from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:

        res = []

        def inorderTree(root, res):

            if root is None:
                return res

            if root.left is not None:
                inorderTree(root.left, res)

            res.append(root.val)

            if root.right is not None:
                inorderTree(root.right, res)

        inorderTree(root, res)

        return res


if __name__ == "__main__":
    root = TreeNode(1)
    level1_right = TreeNode(2)
    level2_left = TreeNode(3)

    root.right = level1_right
    level1_right.left = level2_left

    sol = Solution()
    print(sol.inorderTraversal(root))

（2）迭代解法

假设树为：

　　　　　　　　　　　　　　　   1

　　　　　　　　　　　　　　　/　  \

　　　　　　　　　　　　　　 2　　  3

　　　　　　　　　　　　　  /   \　 /   \

   　　　　　　　　　　　　4     5  6    7

我们使用一个栈来解决问题。步骤如下：

　　　　一，我们将根节点1入栈，如果有左孩子，依次入栈，那么入栈顺序为：1，2，4。由于4的左子树为空，停止入栈，此时栈为{1，2，4}。

　　　　二，此时将4出栈，并遍历4，由于4也没有右孩子，那么根据中序遍历的规则，我们显然应该继续遍历4的父亲2，情况是这样。所以我们继续将2出栈并遍历2，2存在右孩子，将5入栈，此时栈为{1，5}。

　　　　三，5没有孩子，则将5出栈并遍历5，这也符合中序遍历的规则。此时栈为{1}。

　　　　四，1有右孩子，则将1出栈并遍历1，然后将右孩子3入栈，并继续以上三个步骤即可。

　　　　栈的变化过程：{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->{}->{7}->{}。

已经AC的代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res, stack = [], []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                return res
            node = stack.pop()
            res.append(node.val)
            root = node.right

已经AC的代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        res, stack = [], []
        stack.append(root)
        while stack:
            while root and root.left:
                stack.append(root.left)
                root = root.left

            root = stack.pop()
            res.append(root.val)


            root = root.right

            if root:
                stack.append(root)

        return res

Reference：

【1】https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31381/Python-recursive-and-iterative-solutions.

【2】https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31350/Easy-to-understand-Python-code-beats-96.42-Python-submissions

【3】https://www.cnblogs.com/zuoyuan/p/3720273.html