解法一：迭代法

前序遍历先读取root.val，然后按root.right, root.left的顺序压栈。这样在出栈时会先访问left，然后时right。后续遍历参照这种方式，按root.left, root.right的顺序压栈，即迭代顺序为”中右左”，最终将结果倒序即可，变为”左中右”。

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  8. class Solution:
  10.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  11.         ans = []
  12.         if not root:
  13.             return ans
  14.         stack = [root]
  15.         while stack:
  16.             root = stack.pop()
  17.             ans.append(root.val)
  18.             if root.right:
  19.                 stack.append(root.right)
  20.             if root.left:
  21.                 stack.append(root.left)
  22.         return ans
  24.        def inorderTraversal(self, root: TreeNode) -> List[int]:
  25.         ans = []
  26.         if not root:
  27.             return ans
  28.         p = root
  29.         stack = []
  30.         while p or stack:
  31.             # 将p入栈，继续访问其左子树
  32.                if p:
  33.                 stack.append(p)
  34.                 p = p.left
  35.             # 当p为空，即没有左子树可以访问时，p从stack中取到其上一层，访问val
  36.             # 然后再访问右子树
  37.             else:
  38.                 p = stack.pop()
  39.                 ans.append(p.val)
  40.                 p = p.right
  41.         return ans
  43.     def postorderTraversal(self, root: TreeNode) -> List[int]:
  44.         ans = []
  45.         if not root:
  46.             return ans
  47.         stack = [root]
  48.         while stack:
  49.             root = stack.pop()
  50.             ans.append(root.val)
  51.             if root.left:
  52.                 stack.append(root.left)
  53.             if root.right:
  54.                 stack.append(root.right)
  55.         return ans[::-1]