94. 二叉树的中序遍历
image-20201209183728489
递归
递归的实现很简单，和前序遍历类似，只是改变了append到数组的顺序。
# 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]: ans = [] def traversal(root): if root is None: return traversal(root.left) ans.append(root.val) traversal(root.right) traversal(root) return ans
image-20201209184546101
迭代
递归维护了一个隐藏的stack，这里我们需要手动维护这个stack. 以[1, null, 2, 3]为例，进栈出栈顺序为: [1] // 1进栈 [] // 由于1没有left，1出栈 [2] // 2进栈 [2, 3] // 2的left进栈 [2] // 由于3没有left 3出栈 [] // 2出栈
# 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]: stack = [] ans = [] while len(stack) > 0 or root is not None: # 如果root左节点一直有值，则一直进栈 while root is not None: stack.append(root) root = root.left current = stack.pop() ans.append(current.val) # 当前节点出栈后，把右节点赋给root，因为中序遍历是 左孩子 根节点 右孩子 root = current.right return ans
image-20201209184757061
