LeetCode 面试题 04.08. 首个共同祖先

这篇具有很好参考价值的文章主要介绍了LeetCode 面试题 04.08. 首个共同祖先。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

  设计并实现一个算法,找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意:这不一定是二叉搜索树。

  例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

    3
   / \
  5   1
 / \ / \
6  2 0  8
  / \
 7   4

  点击此处跳转题目。

示例 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。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

二、C# 题解

  基本思路为,后序遍历该树,即先访问孩子结点,后访问该结点,因此为自底向上遍历,处理该结点时就已知左右子树的结果。具体情况对应的处理如下:文章来源地址https://www.toymoban.com/news/detail-712483.html

   node
  /    \
left  right
  1. node 为 null:返回 null;
  2. node 为 p 或 q:
    1. 若 left、right 中也有一个为 p 或 q:表示该树已找到 p 和 q,返回 node 并标识已找到;
    2. left、right 均不为 p 或 q:表示第一个找到,返回 node 自己即可;
  3. node 不为 p 或 q:
    1. left、right 均为 p 或 q:表示该树已找到 p 和 q,返回 node 并标识已找到;
    2. left 为 p 或 q 而 right 不是:返回 left,表示该树找只到了一个;
    3. right 为 p 或 q 而 left 不是:返回 right,表示该树找只到了一个;
    4. left、right 均不为 p 或 q:返回 null,表示没找到。
  4. 如果标识出子树已找到结果,则直接返回 left、right 中不为 null 的那一个,那个就记录了第一个共同父亲。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        bool rt = false;
        return Partition(root, p, q, ref rt);
    }

    // DFS 递归,bool rt 用于记录是否已同时找到 p、q
    public TreeNode Partition(TreeNode node, TreeNode p, TreeNode q, ref bool rt) {
        if (node == null) return null;     // 情况 1

        TreeNode left = Partition(node.left, p, q, ref rt);   // 左子树结果
        TreeNode right = Partition(node.right, p, q, ref rt); // 右子树结果

        if (rt) return left == null ? right : left; // 已找到结果,即情况 4

        // 没找到结果,分为以下几种情况
        TreeNode result = null;
        if (node == p || node == q) {      // 情况 2
            if (left == p || left == q || right == p || right == q) rt = true; // 情况 2.1
            result = node;                 // 返回结果为自己
        }
        else if (left == p || left == q) { 
            if (right == p || right == q)  // 情况 3.1
            	{ rt = true; result = node; } 
            else result = left;            // 情况 3.2
        }
        else if (right == p || right == q) // 情况 3.3
            result = right;

        return result;                     // 情况 3.4
    }
}
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

到了这里,关于LeetCode 面试题 04.08. 首个共同祖先的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 面试题 16.08. 整数的英语表示

      给定一个整数,打印该整数的英文描述。 示例 1: 输入: 123 输出: “One Hundred Twenty Three” 示例 2: 输入: 12345 输出: “Twelve Thousand Three Hundred Forty Five” 示例 3: 输入: 1234567 输出: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven” 示例 4: 输入: 1234567891 输出: “One Billi

    2024年02月06日
    浏览(31)
  • LeetCode 面试题 17.08 —— 马戏团人塔

    首先,我们对人的身高按照从小到大排序, 特别注意,对于身高相等的人,要按照体重从高到低排序 。这时候,序列已经满足了在上面的人要比下面的人矮一点,然后,我们只需要保证提取到一个最长的体重的上升子序列即可。这一步骤也就是 LeetCode 300——最长上升子序列

    2024年04月28日
    浏览(27)
  • 【每日一题】Leetcode - 面试题 17.08. Circus Tower LCCI

    Leetcode - 面试题 17.08. Circus Tower LCCI Sorting heights to be ascending order and weights to be descending order. dp[i] = j represents person[i] as the bottom of tower, the tower height is amount of j, to calculate the dp[i] we find the maximum of dp[0 ~ (i-1)] what the person[0 ~ (i-1)] shorter and lighter than person[i], increase it of one, it’s th

    2024年02月13日
    浏览(44)
  • 3-【斐波那契数列模型】LeetCode面试题08.01-三步问题

    题目 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。 示例1: 输入:n = 3  输出:4 说明: 有四种走法 示例2: 输入:n = 5 输出:13 提示:n范围在[1, 1000

    2024年02月05日
    浏览(35)
  • 【手撕算法|动态规划系列No.2】leetcode面试题 08.01. 三步问题

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(62)
  • LeetCode 面试题 02.04. 分割链表

      给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。   你不需要 保留 每个分区中各节点的初始相对位置。   点击此处跳转题目。 示例 1: 输入:head = [1,4,3,2,5,2], x = 3 输出:[1,2,2,4,3,5] 示例

    2024年02月11日
    浏览(36)
  • LeetCode 面试题 04.01. 节点间通路

      节点间通路。给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。   点击此处跳转题目。 示例1: 输入: n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2 输出: true 示例2: 输入: n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3],

    2024年02月09日
    浏览(32)
  • LeetCode 面试题 03.04. 化栈为队

      实现一个MyQueue类,该类用两个栈来实现一个队列。   点击此处跳转题目。 示例: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false 说明: 你只能使用标准的栈操作 – 也就是只有 push to top , peek/pop from top , s

    2024年02月09日
    浏览(36)
  • Leetcode面试经典150题刷题记录 —— 数学篇

    Leetcode面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试经典

    2024年01月21日
    浏览(56)
  • Leetcode面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年01月16日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包