236.二叉树的最近公共祖先

LeetCode LeetCode 树 深度优先搜索 二叉树
发布时间 :
字数:1.8k 阅读 : 评论:
  1. 236.二叉树的最近公共祖先
    1. 236.1 题目
    2. 236.2 题解
      1. 递归查找
      2. 带父指针的深度优先搜索
    3. 236.3 代码
    4. 236.4 运行结果

236.二叉树的最近公共祖先

236.1 题目

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

  • 树中节点数目在范围 [2, 10^5] 内。
  • -10^9 <= Node.val <= 10^9
  • 所有 Node.val 互不相同。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

236.2 题解

递归查找

// 方法一：递归查找
// 通过递归找到最近公共祖先
static TreeNode LowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q)
{
    return LowestCommonAncestorRecursive(root, p, q);
}

// 递归函数，用于查找最近公共祖先
static TreeNode LowestCommonAncestorRecursive(TreeNode root, TreeNode p, TreeNode q)
{
    // 如果当前节点为空或等于p或q，直接返回当前节点
    if (root == null || root == p || root == q)
    {
        return root;
    }

    // 递归查找左子树和右子树
    TreeNode left = LowestCommonAncestorRecursive(root.left, p, q);
    TreeNode right = LowestCommonAncestorRecursive(root.right, p, q);

    // 如果左子树和右子树都不为空，说明p和q分别位于当前节点的两侧，返回当前节点
    if (left != null && right != null)
    {
        return root;
    }

    // 否则返回不为空的那个子树
    return left ?? right;
}

带父指针的深度优先搜索

// 方法二：带父指针的深度优先搜索
// 使用哈希表存储每个节点的父节点，通过父节点查找最近公共祖先
static TreeNode LowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q)
{
    // 哈希表存储每个节点的父节点
    var parent = new Dictionary<TreeNode, TreeNode>();
    // 栈用于深度优先搜索
    var stack = new Stack<TreeNode>();

    // 初始化：根节点没有父节点
    parent[root] = null;
    stack.Push(root);

    // 直到找到p和q的父节点为止
    while (!parent.ContainsKey(p) || !parent.ContainsKey(q))
    {
        var node = stack.Pop();

        // 如果左子节点不为空，记录左子节点的父节点，并将左子节点入栈
        if (node.left != null)
        {
            parent[node.left] = node;
            stack.Push(node.left);
        }

        // 如果右子节点不为空，记录右子节点的父节点，并将右子节点入栈
        if (node.right != null)
        {
            parent[node.right] = node;
            stack.Push(node.right);
        }
    }

    // 哈希集合存储p节点及其所有祖先
    var ancestors = new HashSet<TreeNode>();

    // 记录p节点及其所有祖先
    while (p != null)
    {
        ancestors.Add(p);
        p = parent[p];
    }

    // 找到q的最近公共祖先
    while (!ancestors.Contains(q))
    {
        q = parent[q];
    }

    return q;
}

236.3 代码

using System;
using System.Collections.Generic;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
        // 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
        // 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

        // 示例 1：
        // 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
        // 输出：3
        // 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

        // 示例 2：
        // 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
        // 输出：5
        // 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

        // 示例 3：
        // 输入：root = [1,2], p = 1, q = 2
        // 输出：1

        // 提示：
        // 树中节点数目在范围 [2, 105] 内。
        // -109 <= Node.val <= 109
        // 所有 Node.val 互不相同 。
        // p != q
        // p 和 q 均存在于给定的二叉树中。

        #endregion

        #region 测试

        // 示例 1
        TreeNode root1 = new TreeNode(3,
            new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))),
            new TreeNode(1, new TreeNode(0), new TreeNode(8)));
        TreeNode p1 = root1.left; // 5
        TreeNode q1 = root1.right; // 1
        TreeNode result1 = LowestCommonAncestor1(root1, p1, q1);
        Console.WriteLine($"示例1 方法1 输出：{result1.val}");
        TreeNode result1_2 = LowestCommonAncestor2(root1, p1, q1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2.val}");

        // 示例 2
        TreeNode root2 = new TreeNode(3,
            new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))),
            new TreeNode(1, new TreeNode(0), new TreeNode(8)));
        TreeNode p2 = root2.left; // 5
        TreeNode q2 = root2.left.right.right; // 4
        TreeNode result2 = LowestCommonAncestor1(root2, p2, q2);
        Console.WriteLine($"示例2 方法1 输出：{result2.val}");
        TreeNode result2_2 = LowestCommonAncestor2(root2, p2, q2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2.val}");

        // 示例 3
        TreeNode root3 = new TreeNode(1, new TreeNode(2));
        TreeNode p3 = root3; // 1
        TreeNode q3 = root3.left; // 2
        TreeNode result3 = LowestCommonAncestor1(root3, p3, q3);
        Console.WriteLine($"示例3 方法1 输出：{result3.val}");
        TreeNode result3_2 = LowestCommonAncestor2(root3, p3, q3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2.val}");

        #endregion
    }

    #region 答案

    // 方法一：递归查找
    // 通过递归找到最近公共祖先
    static TreeNode LowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q)
    {
        return LowestCommonAncestorRecursive(root, p, q);
    }

    // 递归函数，用于查找最近公共祖先
    static TreeNode LowestCommonAncestorRecursive(TreeNode root, TreeNode p, TreeNode q)
    {
        // 如果当前节点为空或等于p或q，直接返回当前节点
        if (root == null || root == p || root == q)
        {
            return root;
        }

        // 递归查找左子树和右子树
        TreeNode left = LowestCommonAncestorRecursive(root.left, p, q);
        TreeNode right = LowestCommonAncestorRecursive(root.right, p, q);

        // 如果左子树和右子树都不为空，说明p和q分别位于当前节点的两侧，返回当前节点
        if (left != null && right != null)
        {
            return root;
        }

        // 否则返回不为空的那个子树
        return left ?? right;
    }

    // 方法二：带父指针的深度优先搜索
    // 使用哈希表存储每个节点的父节点，通过父节点查找最近公共祖先
    static TreeNode LowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q)
    {
        // 哈希表存储每个节点的父节点
        var parent = new Dictionary<TreeNode, TreeNode>();
        // 栈用于深度优先搜索
        var stack = new Stack<TreeNode>();

        // 初始化：根节点没有父节点
        parent[root] = null;
        stack.Push(root);

        // 直到找到p和q的父节点为止
        while (!parent.ContainsKey(p) || !parent.ContainsKey(q))
        {
            var node = stack.Pop();

            // 如果左子节点不为空，记录左子节点的父节点，并将左子节点入栈
            if (node.left != null)
            {
                parent[node.left] = node;
                stack.Push(node.left);
            }

            // 如果右子节点不为空，记录右子节点的父节点，并将右子节点入栈
            if (node.right != null)
            {
                parent[node.right] = node;
                stack.Push(node.right);
            }
        }

        // 哈希集合存储p节点及其所有祖先
        var ancestors = new HashSet<TreeNode>();

        // 记录p节点及其所有祖先
        while (p != null)
        {
            ancestors.Add(p);
            p = parent[p];
        }

        // 找到q的最近公共祖先
        while (!ancestors.Contains(q))
        {
            q = parent[q];
        }

        return q;
    }

    #endregion
}

236.4 运行结果

示例1 方法1 输出：3
示例1 方法2 输出：3
示例2 方法1 输出：5
示例2 方法2 输出：5
示例3 方法1 输出：1
示例3 方法2 输出：1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏