解题思路
预备知识：
- 二叉树结构基础
- 中序遍历是什么
什么是中序遍历
有个口诀叫：左根右
意思就是在遍历过程中，先找到根节点然后会去找左子节点，如果有左子节点就继续在往下找，直到找到最地下一层的左子节点。如果没有左子节点就返回根节点，最后才返回右子节点。
如图：
中序遍历最终返回的顺序为：BDCAEHGKF
递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if not root: return
self.dfs(root.left, res)
res.append(root.val)
self.dfs(root.right, res)
复杂度分析
- 时间复杂度 O(N)
- 空间复杂度 O(logN), 最坏情况是O(N)
迭代法
迭代法的思路和递归法一样，先遍历左子树，然后是根节点随后再是右子树。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
res = []
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
复杂度分析
- 时间复杂度 O(N)
- 空间复杂度 O(N)