给定一个二叉树的根节点 root ,返回它的 中序 遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
#最直观的思路
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
# 递归
# def dfs(root:TreeNode):
# if not root:
# return
# dfs(root.left)
# res.append(root.val)
# dfs(root.right)
# res = []
# dfs(root)
# return res
#迭代
stack, res = [], []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
# print(root)
res.append(root.val)
root = root.right
# print(root)
return res