二叉树遍历与常见问题求解

原创

疯狂的KK

发布于 2023-09-26 10:05:48

2570

发布于 2023-09-26 10:05:48

文章被收录于专栏：Java项目实战

引言

欢迎各位读者阅读本篇技术博客！二叉树是计算机科学中常见的数据结构，它的特性和应用无处不在。本文将重点介绍二叉树的前序、中序和后序遍历，并讨论如何利用这些遍历方式解决一些常见的问题，包括查找两个节点的最近公共祖先和计算两个节点之间的距离。通过本文的学习，您将深入了解这些核心概念，并获得代码示例来应对实际问题。

前序、中序和后序遍历

在开始讨论问题解决方案之前，我们需要了解二叉树的三种常见遍历方式：前序遍历、中序遍历和后序遍历。

前序遍历

前序遍历是一种深度优先遍历方式，它首先访问根节点，然后递归地遍历左子树和右子树。前序遍历的伪代码如下：

def preorder(node):
    if node is not None:
        # 访问当前节点
        visit(node)
        # 递归遍历左子树
        preorder(node.left)
        # 递归遍历右子树
        preorder(node.right)

中序遍历

中序遍历同样是一种深度优先遍历方式，但它的顺序是先遍历左子树，然后访问根节点，最后遍历右子树。中序遍历的伪代码如下：

def inorder(node):
    if node is not None:
        # 递归遍历左子树
        inorder(node.left)
        # 访问当前节点
        visit(node)
        # 递归遍历右子树
        inorder(node.right)

后序遍历

后序遍历同样是深度优先遍历，它的顺序是先遍历左子树，然后遍历右子树，最后访问根节点。后序遍历的伪代码如下：

def postorder(node):
    if node is not None:
        # 递归遍历左子树
        postorder(node.left)
        # 递归遍历右子树
        postorder(node.right)
        # 访问当前节点
        visit(node)

最近公共祖先问题

问题描述

给定一个二叉树，找到两个节点的最近公共祖先（Lowest Common Ancestor, LCA）。

解决方案

为了解决这个问题，我们可以利用二叉树的性质和遍历方式。首先，我们从根节点开始进行后序遍历。在遍历过程中，我们检查当前节点是否等于其中一个目标节点。如果等于，我们返回当前节点作为一个潜在的公共祖先。然后，我们递归地查找左子树和右子树，分别得到左子树和右子树中的潜在公共祖先。最后，我们根据左右子树的结果来确定最终的最近公共祖先。

以下是解决方案的示例代码：

def lowestCommonAncestor(root, p, q):
    if root is None:
        return None
    
    if root == p or root == q:
        return root
    
    left_lca = lowestCommonAncestor(root.left, p, q)
    right_lca = lowestCommonAncestor(root.right, p, q)
    
    if left_lca and right_lca:
        return root
    elif left_lca:
        return left_lca
    else:
        return right_lca

节点距离问题

问题描述

给定一个二叉树和两个节点，找出这两个节点的距离（即从一个节点到另一个节点的最短路径上的边数）。

解决方案

要解决节点距离问题，我们可以分为三个步骤：首先，找到这两个节点的最近公共祖先；然后，分别计算从最近公共祖先到这两个节点的距离；最后，将这两个距离相加即可得到节点距离。

def findDistance(root, p, q):
    # 辅助函数，用于计算从根节点到目标节点的距离
    def findDepth(node, target):
        if node is None:
            return -1
        if node == target:
            return 0
        left_depth = findDepth(node.left, target)
        right_depth = findDepth(node.right, target)
        if left_depth != -1:
            return left_depth + 1
        elif right_depth != -1:
            return right_depth + 1
        else:
            return -1

    lca = lowestCommonAncestor(root, p, q)
    distance_p = findDepth(lca, p)
    distance_q = findDepth(lca, q)
    
    return distance_p + distance_q