DFS

方法一DFS

参考代码

  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
  7. class Solution:
  8.     def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  9.         ans = []
  10.         def dfs(root):
  11.             if not root:
  12.                 return
  13.             dfs(root.left)
  14.             ans.append(root.val)
  15.             dfs(root.right)
  16.         dfs(root)
  17.         return ans

复杂度分析

时间复杂度O(n)
空间复杂度O(n)