Binary Tree Traversal 二叉树遍历。

前序、中序、后序遍历用到的数据结构都是栈,使用 Python 的 list 来表示栈,有 append()pop() 方法,都是 O(1) 时间。需要注意的是 list 的带参数的 pop(i) 复杂度是 O(n) 。(所以一般如果要用队列的话最好不要用 list 而是用 collections.deque()append()popleft() 来达到 O(1) 。)

# 前序遍历

LeetCode 模板题:144. 二叉树的前序遍历

顺序是根左右

递归版:

preorder-recur.py
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

迭代算法的思路是使用一个栈,每次操作从栈顶弹出一个结点来操作,把结点的值放到结果列表中,再依次压入右结点、左结点。

迭代版:

preorder-iter-1.py
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        ans = []
        stk = [root]
        while stk:
            node = stk.pop()
            ans.append(node.val)
            if node.right: stk.append(node.right)
            if node.left: stk.append(node.left)
        return ans

# 中序遍历

LeetCode 模板题:94. 二叉树的中序遍历

顺序是左根右

inorder-recur.py
# 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: Optional[TreeNode]) -> List[int]:
        if not root: return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

迭代算法的思路是从根节点开始,将每个考察到的结点压入栈中,然后走向他的左结点,直到左节点为空时停止,弹出栈顶的结点并将这个结点的值放到结果列表中,之后考察其右节点,继续循环。

inorder-iter-1.py
# 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: Optional[TreeNode]) -> List[int]:
        if not root: return []
        ans, stk, node = [], [], root
        while node or stk:
            while node:
                stk.append(node)
                node = node.left
            node = stk.pop()
            ans.append(node.val)
            node = node.right
        return ans

中序遍历的这种写法很容易推广到前序和后序,之后会说这样的统一写法。

# 后序遍历

LeetCode 模板题:145. 二叉树的后序遍历

顺序是左右根

递归版:

postorder-recur.py
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

迭代算法的思路有两种。

一种是观察后序遍历和先序遍历的联系,后序是左右根,先序是根左右,可以很轻易的稍微改一改先序的程序,使之输出根右左,然后把结果反转一下就是最终结果左右根

另一种是记录之前访问到的最前面的右结点 lastVisit ,访问到一个结点时,如果上一个访问到的就是这个结点的右结点,则可以把这个结点的值放入结果列表,并且更新栈和 lastVisit 。如果不是,则访问它的右结点即可。

下面分别是这两种方法。反转根右左:

postorder-iter-1.py
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        ans = []
        stk = [root]
        while stk:
            node = stk.pop()
            ans.append(node.val)
            if node.left: stk.append(node.left)
            if node.right: stk.append(node.right)
        return ans[::-1]

记录上一个右结点:

postorder-iter-2.py
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        ans = []
        stk = []
        node = lastVisit = root
        while node or stk:
            while node:
                stk.append(node)
                node = node.left
            if stk[-1].right and stk[-1].right != lastVisit:
                node = stk[-1].right
            else:
                ans.append(stk[-1].val)
                lastVisit = stk[-1]
                stk.pop()
        return ans

# 前序中序后序统一写法

话不多说,直接把代码放到一起。

前序遍历:

preorder-iter-2.py
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        ans, stk, node = [], [], root
        while node or stk:
            while node:
                ans.append(node.val)
                stk.append(node)
                node = node.left
            node = stk.pop()
            node = node.right
        return ans

中序遍历:

inorder-iter-1.py
# 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: Optional[TreeNode]) -> List[int]:
        if not root: return []
        ans, stk, node = [], [], root
        while node or stk:
            while node:
                stk.append(node)
                node = node.left
            node = stk.pop()
            ans.append(node.val)
            node = node.right
        return ans

后序遍历:

postorder-iter-3.py
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        ans, stk, node = [], [], root
        while node or stk:
            while node:
                ans.append(node.val)
                stk.append(node)
                node = node.right
            node = stk.pop()
            node = node.left
        return ans[::-1]

三种算法都可以用相似的方式实现出来,这就是前序中序后序统一写法,方便记忆。