• 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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

      点击此处跳转题目

    示例 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# 题解

      基本思路为,后序遍历该树,即先访问孩子结点,后访问该结点,因此为自底向上遍历,处理该结点时就已知左右子树的结果。具体情况对应的处理如下:

       node
      /    \
    left  right
    
    • 1
    • 2
    • 3
    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
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)
  • 相关阅读:
    TS中的info用法
    面试中的最常被问到的两种锁
    程序员之友:注释的重要性与最佳实践(InsCode AI 创作助手)
    Content-Type的取值
    力扣每日一题60:排序序列
    算法基础学习|二分
    python 归并排序
    DevOps|服务治理与服务保障实践指南
    PbootCms微信小程序官网模版/企业官网/社交电商官网/网络工作室/软件公司官网
    【Python】Labelme/PIL读取图片朝向错误解决
  • 原文地址:https://blog.csdn.net/zheliku/article/details/132863007