本文最后更新于:2 个月前

一、二叉树

二叉树是一种更为典型的树树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。下面是个二叉树的例子:
图1
用python定义二叉树的节点:

# 二叉树节点
class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

二、二叉树遍历

1、前序遍历

前序遍历访问的顺序为:根节点、左子树、右子树。对于上图,遍历过程如下:

  • 一开始指向根节点,访问它,为E
  • 有左子树,指向他并访问,为A
  • A没有左子树,指向其右子树并访问,为C
  • C有左子树和右子树,按顺序访问,为BD
  • E的左半边访问完毕,指向E的右子树并访问,为G
  • G只有右子树,访问它,为F
  • F往下已经没有叶子节点,遍历结束

因此,前序遍历的结果为:EACBDGF

2、中序遍历

中序遍历访问的顺序为:左子树、根节点、右子树。对于上图,遍历过程如下:

  • 一开始指向根节点E,因为优先访问左子树,先看有没有左子树。发现根节点有左子树A,指向它
  • 此时A有没有左子树,因此访问当前节点,为A
  • A有右子树,指向其右子树C
  • 此节点C有左子树,指向其左子树B
  • 此时节点没有子树,访问其节点为B
  • 然后往回指向节点B的父节点,并访问,为C
  • C有右子树,访问,为D
  • 此时指回根节点E,访问它,为E
  • E有右子树,指向右子树G
  • 因为G没有左子树,因此访问当前节点,为G
  • G有右子树,访问,为F
  • F无子树,遍历结束

因此,中序遍历的结果为:ABCDEGF。通常来说,对于二叉搜索树,我们可以通过中序遍历得到一个递增的有序序列

3、后序遍历

后序遍历访问的顺序为:左子树、右子树、根节点。对于上图,遍历过程如下:

  • 一开始指向根节点E,先指向左子树A
  • 要优先访问左子树右子树,A无左子树、有右子树,因此指向A的右子树C
  • C有左子树,指向左子树B
  • B无子树,访问为B
  • 指回C,C有右子树,指向并访问,为D
  • 指回BD的根节点C,访问为C
  • 指回C的根节点,访问为A
  • 指回A的根节点E,访问其右子树G
  • G有右子树,访问为F
  • 指回F的根节点,访问为G
  • 指回G的根节点,访问为E
  • E已为整个树的根节点,遍历结束

因此,后序遍历的结果为:BDCAFGE。当你删除树中的节点时,用到后序遍历。 也就是说,当你删除一个节点时,你将首先删除它的左节点和它的右边的节点,然后再删除节点本身。

4、层序遍历

层序遍历就是逐层遍历树结构,下图展示了它的层次结构:
在这里插入图片描述
二叉树的层序遍历即为广度优先搜索,该算法从一个根节点开始,首先访问节点本身。 然后遍历它的相邻节点,其次遍历它的二级邻节点、三级邻节点,以此类推。广度优先搜索需要用到队列。遍历过程如下:

  • 初始化队列q=[],并将根节点E入队,为q=[E]
  • q出队,为E
  • E有左子树和右子树,两者入队,为q=[A, G]
  • q出队,为A,此时将A的右子树入队,为q=[G, C]
  • q出队,为G,此时G的右子树入队,为q=[C, F]
  • q出队,为C,此时C的左子树、右子树入队,为q=[F, B, D]
  • q出队,为F,此时q=[B, D]
  • F没有子树,q继续出队,为B,此时q=[D]
  • q出队,为D
  • q为空,遍历结束

因此,层序遍历的结果为:EAGCFBD

三、程序实现

二叉树的前序、中序、后序和层序遍历,分别为leetcode的第144、94、145、102题,都可以用递归迭代两种方法做。

1、递归实现

对于前序、中序和后序来说,递归的现实非常简单,他们的实现区别是根节点访问的顺序不一样。代码如下:

# 前序遍历递归
class Solution:
	def preorderTraversal(self, root: TreeNode) -> List[int]:
		if not root:
			return []
		else:
			return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
# 中序遍历递归
class Solution:
	def inorderTraversal(self, root: TreeNode) -> List[int]:
		if not root:
			return []
		else:
			return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
# 后序遍历递归
class Solution:
	def postorderTraversal(self, root: TreeNode) -> List[int]:
		if not root:
			return []
		else:
			return self.postorderTraversal(root.left)  + self.postorderTraversal(root.right)+ [root.val]

可以看出不同的地方就是[root.val]的位置不一样,前序遍历[root.val]就在最一开始,中序遍历[root.val]则在中间,后序遍历[root.val]就在最后。整个迭代结构下图所示:

在这里插入图片描述

对于层序遍历的递归实现,我们不仅要输出层序遍历的序列,还要有每个元素属于哪个层次的信息,可以用列表嵌套的方式,比如之前的例子里,层序遍历表示为[[E], [AG], [CF], [BD]]

# 层序遍历递归
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
		levels = []
        if not root:
            return levels
        
        def helper(node, level):
            # start the current level
            if len(levels) == level:
                levels.append([])

            # append the current node value
            levels[level].append(node.val)

            # process child nodes for the next level
            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)
            
        helper(root, 0)
        return levels

我们设更节点的层级序号为0,依次往下为1、2、3……。leaves为保存结果的列表,每一层的结果又为一个列表,保存在leaves里,层级序号即为在leaves里的index,在第i层级,leaves里应该有i+1个列表,第i+1个列表为当前层级的节点。每个列表只append层级序号相同的节点。

2、迭代实现

二叉树的迭代实现都需要用到。对于前序、中序、后序遍历,他们的迭代实现大同小异:

# 前序遍历迭代
class Solution:        
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        stack, output = [root, ], []
        while stack:
            root = stack.pop()
            if root is not None:
                output.append(root.val)
                if root.right is not None:
                    stack.append(root.right)
                if root.left is not None:
                    stack.append(root.left)

        return output
# 中序遍历迭代
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
    	if root is None:
            return []
            
        stack, output= [], []
        curr = root
        while curr or len(stack) > 0:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            output.append(curr.val)
            curr = curr.right
        return output
# 后序遍历迭代
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        stack, output = [root, ], []
        while stack:
            root = stack.pop()
            output.append(root.val)
            if root.left is not None:
                stack.append(root.left)
            if root.right is not None:
                stack.append(root.right)
                
        return output[::-1]
  • 对于前序遍历,先初始化一个有根节点的栈,然后进入循环,出栈根节点,访问它。然后依次入栈右子树、左子树(注意栈是先进后出)。则下次循环,会先出栈左子树,访问它,然后入栈它的右子树、左子树。这样根节点E的右子树会在其左子树遍历完后才会出栈。循环停止条件是栈为空。
  • 对于中序遍历,因为要优先遍历左子树,循环之前初始化一个空栈,进入循环后,用一个内循环依次入栈左子树,直到叶子节点(也为一个左子树),然后退出内循环,出栈并访问。
  • 对于后序遍历,和前序遍历的整体结构是一样的,唯一不同的是在循环里先入栈左子树,后入栈右子树,循环结束后将结果逆序。

对于层序遍历的迭代实现,循环之前初始化一个有根节点的队列,此时队列只有一个元素,进入循环后,出队并访问,然后将根节点的左右子树依次入队。下次循环,依次将上次队列里的元素出队,同队入队他们的左右子树。这样每次循环只出队当前层次的节点,并入队他们的左右子树,完成了层次之间的交换。这实际上是一种广度优先搜索层序遍历迭代写法:

# 层序遍历迭代,使用栈
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        q = [root]
        result = []
        while q:
            res = []
            for i in range(len(q)):
                node = q.pop(0)
                res.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(res)
        return result
# 层序遍历迭代,使用队列
from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
            
        res = []
        q = deque()
        q.append(root)
        while q:
            size = len(q)
            curr_level = []
            for _ in range(size):
                node = q.popleft()
                curr_level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(curr_level)
        return res

四、例题

二叉树的最近公共祖先

此题为leetcode第236题

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 树为空返回None
        if root is None:
            return None
        
        # 找到了p或q
        if root == p or root == q:
            return root
        
        # 在root的左子树找p或q
        left = self.lowestCommonAncestor(root.left, p, q)
        # 在root的右子树找p或q
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left is None:    # 如果左子树没有p或q,返回右孩子
            return right
        elif right is None: # 如果右子树没有p或q,返回左孩子
            return left
        else:               # 如果分别在左右子树找到了p或q,那么root就是最近公共祖先
            return root

五、总结

  • 前序、中序、后序遍历的递归实现几乎一模一样,区别是根节点的访问位置不一样
  • 前序、中序、后序的迭代实现需要借助栈
  • 层序遍历的递归和迭代实现需要借助队列