[LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历

亦凉 2022-01-10 16:45 195阅读 0赞

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

示例:

输入: \[1,null,2,3\]  
   1  
    \\  
     2  
    /  
   3

输出: \[1,3,2\]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解法：

二叉树的中序遍历顺序为左-根-右，可以有递归和非递归来解，非递归解法又分为两种，一种是使用栈来接，另一种不需要使用栈的Morris方法。

Morris方法可参考帖子：[Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）][Morris Traversal_O_1]

python的递归代码：

class Solution(object):
        def inorderTraversal(self, root):
            res = []
            if root:
                res = self.inorderTraversal(root.left) 
                res.append(root.val)
                res = res + self.inorderTraversal(root.right)
            return res

python非递归使用栈代码：

class Solution2(object):
        def inorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            result, stack = [], [(root, False)]
            while stack:
                root, is_visited = stack.pop()
                if root is None:
                    continue
                if is_visited:
                    result.append(root.val)
                else:
                    stack.append((root.right, False))
                    stack.append((root, True))
                    stack.append((root.left, False))
            return result

[Morris Traversal_O_1]: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html