@liweiwei1419 2019-02-10T15:23:41.000000Z 字数 965 阅读 984

# 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 = Noneclass 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 = Noneclass 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

（本节完）

• 私有
• 公开
• 删除