LeetCode 94.二叉树的中序遍历——Python实现（二叉树，栈）

1、用递归的方式实现

class Solution(object):def inorderTraversal(self, root: TreeNode):if root is None:return []return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

2、用栈的方式实现（这个方法太难懂了）

class Solution(object):def inorderTraversal(self, root: TreeNode):if root is None:return []stack, output = [], []current = rootwhile current or stack:while current:stack.append(current)current = current.left# 默认每个节点的左子树已经处理了，现在只用处理当前节点和右子树，因为右子树也是一样的处理方式，所以当前节点要切换到右子树current = stack.pop()output.append(current.val)current = current.rightreturn output