一文搞懂二叉树中序遍历的三种方法

系列文章：

相关题目：
94. 二叉树的中序遍历

中序遍历结果为：4 2 5 1 6 3 7

总体上分为两种框架，递归框架和非递归框架，递归框架又分为两种思路：分解思路和遍历思路。

• 递归
  1、分解思路 【分解为子问题】
  2、遍历思路 【更新外部变量】
• 非递归
  3、借助栈

下面代码对三种方法逐一实现。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class InorderTraversal:
    """
    94. 二叉树的中序遍历
    https://leetcode.cn/problems/binary-tree-inorder-traversal/
    """

    def solution1(self, root):
        """
        中序遍历
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        return self.solution1(root.left) + [root.val] + self.solution1(root.right)

    def solution1_1(self, root):
        """
        分解思路，同上
        :param root:
        :return:
        """
        res = []
        if not root:
            return []

        res.extend(self.solution1_1(root.left))
        res.append(root.val)
        res.extend(self.solution1_1(root.right))

        return res

    def solution2(self, root):
        """
        遍历思路，一般需要借助递归函数，递归函数没有返回值，靠更新外部变量得到结果
        :param root:
        :return:
        """
        self.res = []
        self.traverse(root)
        return self.res

    def traverse(self, node):
        if not node:
            return

        self.traverse(node.left)
        self.res.append(node.val)
        self.traverse(node.right)

    def solution3(self, root):
        """
        非递归思路，借助栈 实现
        :param root:
        :return:
        """
        res = []
        if not root:
            return res
        else:
            stk = []
            while stk or root:
                if root:
                    stk.append(root)
                    root = root.left
                else:
                    root = stk.pop()
                    res.append(root.val)
                    root = root.right

        return res