递归

1 # Definition for a binary tree node. 2 # class TreeNode: 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.left = None 6 #         self.right = None 7  8 class Solution: 9     def inorderTraversal(self, root: TreeNode) -> List[int]:10         if not root:11             return []12         return self.inorderTraversal(root.left)+ [root.val]+ self.inorderTraversal(root.right)

非递归

1 class Solution: 2     def inorderTraversal(self, root: TreeNode) -> List[int]: 3         stack=[] 4         res=[] 5         while root or stack: 6             if root: 7                 stack.append(root) 8                 root=root.left 9             else:10                 root = stack.pop()11                 res.append(root.val)12                 root=root.right13         return res