LeetCode 第 94 题：中序遍历二叉树

栈

传送门：二叉树的中序遍历。

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

示例:

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

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

分析：左结点一直入栈，然后出栈的时候，当前结点有右边结点的就变成右边结点。

解法1：教科书上的写法

Python 代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res

解法2：万能解法

之所以称之为“万能”，是因为只要改变入栈的顺序，这个模板可以完成“前序遍历”和“中序遍历”。

Python 代码：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def inorderTraversal(self, root):
        if not root:
            return []
        stack = [(1, root)]
        res = []
        while stack:
            command, node = stack.pop()
            if command == 0:
                res.append(node.val)
            else:
                if node.right:
                    stack.append((1, node.right))
                stack.append((0, node))
                if node.left:
                    stack.append((1, node.left))
        return res

（本节完）