中序遍历（递归，分治，栈，Morrios）

递归

def inorderTraversalHelper(self, root):
        if root == None:
            return
        self.inorderTraversalHelper(root.left)    
        self.result.append(root.val)
        self.inorderTraversalHelper(root.right)
        
    def inorderTraversal(self, root):
        # write your code here
        self.result = []
        self.inorderTraversalHelper(root)
        return self.result

分治

def inorderTraversalHelper(self, root):
        if root == None:
            return []
        left = self.inorderTraversalHelper(root.left)    
        mid = [root.val]
        right = self.inorderTraversalHelper(root.right)
        
        return left + mid + right
    def inorderTraversal(self, root):
        
        return self.inorderTraversalHelper(root)

栈

def inorderTraversal(self, root):
        result = []
        stack = []
        node = root
        
        while len(stack) != 0 or node:
            #一直沿左走，走到底
            while node:
                stack.append(node)
                node = node.left
            #把顶部节点出栈，访问
            node = stack.pop()
            result.append(node.val)
            
            #当前指针指向右节点
            #继续重复上述步骤
                #如果右节点为空，则继续访问栈中节点
                #如果右节点不为空，则一直沿左走，走到底，加入栈
            node = node.right
            
        return result

Morrios

文章解释

        node = root
        leftTreeRoot = None
        result = []
        while node:
            leftTreeRoot = node.left
            if leftTreeRoot:
                while leftTreeRoot.right and leftTreeRoot.right != node:
                    leftTreeRoot = leftTreeRoot.right
                if leftTreeRoot.right == None:
                    leftTreeRoot.right = node
                    node = node.left
                    continue
                else:
                    leftTreeRoot.right = None
            
            result.append(node.val)
            node = node.right
            
        return result