递归
思路:
先遍历左子树，再访问根节点，再遍历右子树。
代码：
# 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]: def helper(root,res): if root: if root.left: helper(root.left,res) res.append(root.val) if root.right: helper(root.right,res) res = [] helper(root,res) return res
迭代
思路:
创建一个栈，从根节点遍历左子树，将对应根节点和左子树压入栈中，直到左子树为空。此时取出栈顶节点，将对应节点的值记录，继续对取出节点的右子树进行压栈和取出记录操作，取出的栈顶元素如果右子树为空，则记录后继续取出栈顶节点。
代码：
# 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 = [] stack = [] cur = root while cur or stack: while cur: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right return res
原文：https://www.cnblogs.com/nilhxzcode/p/13167884.html