二叉树的中序遍历

题目链接

示例:
输入: [1,null,2,3]
  1
    \
      2
    /
  3
输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

题目解析

迭代算法，本质上是在模拟递归的过程，递归的时候程序维护了一个隐式的栈来保存节点，迭代算法需要显示维护一个栈。

解题方法

递归算法

中序遍历

递归算法非常简单，对于中序遍历来说，只需要先一直递归左子节点，再访问父节点，最后再递归右子节点。

# 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 dfs(node):
            #终止条件是node为None
            if not node:
                return 
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        result=[]
        dfs(root)
        return result

先序遍历

先序遍历是先访问根节点，再访问左右节点。
我们只需要改变递归调用的顺序即可，代码如下：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(node):
            #终止条件是node为None
            if not node:
                return 
            result.append(node.val)
            dfs(node.left)
            dfs(node.right)
        result=[]
        dfs(root)
        return result

后序遍历

以此类推，后序遍历也可以轻松实现：

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(node):
            #终止条件是node为None
            if not node:
                return 
            dfs(node.left)
            dfs(node.right)
            result.append(node.val)
        result=[]
        dfs(root)
        return result

迭代算法

前面说到，我们需要显示维护一个栈，python中栈和队列都可以使用collections里的deque。

deque的常用操作如下

queue=collections.deque(['a','b','c']) #初始化队列
# 添加元素
queue.append('d') #'a','b','c','d'
queue.appendleft('e') #'e','a','b','c','d'

# 访问元素
queue[0] # 'e'
quque[-1] # 'd'

# 弹出元素
quque.pop() # 从右边弹出 'e','a','b','c'
quque.popleft() # 从左边弹出 'a','b','c'

中序遍历

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack=collections.deque([])
        cur_node=root
        result=[]
        while cur_node or que:
            # 尽量插入左子节点
            while cur_node:
                stack.append(cur_node)
                cur_node=cur_node.left
            # 获得最底层左子节点，该节点无左子节点
            cur_node = stack.pop()
            # 访问该节点的值
            result.append(cur_node.val)
            # 访问该节点的右子节点
            cur_node=cur_node.right
        return result

先序遍历

观察后序遍历的代码，先把所有左子节点入栈，再从最底层访问。先序遍历的顺序和此过程恰好相反，需要从根节点开始访问左子节点。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = collections.deque([])
        cur_node = root
        result=[]
        while cur_node or stack:
            #在插入左子节点的同时保存每个节点的值
            while cur_node:
                stack.append(cur_node)
                result.append(cur_node.val)
                cur_node=cur_node.left
            cur_node=stack.pop()
            cur_node=cur_node.right
        return result

后序遍历

二叉树的后序遍历其实就是二叉树的广度优先搜索之后进行逆序。

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        stack=collections.deque([root])
        result=[]
        while stack:
            cur_node=stack.pop()
            result.append(cur_node.val)
            if cur_node.left is not None:
                stack.append(cur_node.left)
            if cur_node.right is not None:
                stack.append(cur_node.right)
        return result[::-1]