领扣LintCode算法问题答案-88. 最近公共祖先

    科技2025-05-06  86

    领扣LintCode算法问题答案-88. 最近公共祖先

    目录

    88. 最近公共祖先描述样例 1:样例 2: 题解鸣谢

    88. 最近公共祖先

    描述

    给定一棵二叉树,找到两个节点的最近公共父节点(LCA)。

    最近公共祖先是两个节点的公共的祖先节点且具有最大深度。

    假设给出的两个节点都在树中存在

    样例 1:

    输入:{1},1,1 输出:1 解释: 二叉树如下(只有一个节点): 1 LCA(1,1) = 1

    样例 2:

    输入:{4,3,7,#,#,5,6},3,5 输出:4 解释: 二叉树如下: 4 / \ 3 7 / \ 5 6 LCA(3, 5) = 4

    题解

    /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /* * @param root: The root of the binary search tree. * @param A: A TreeNode in a Binary. * @param B: A TreeNode in a Binary. * @return: Return the least common ancestor(LCA) of the two nodes. */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) { // write your code here if (root == null) { return null; } if (root == A || root == B) { return root; } TreeNode left = lowestCommonAncestor(root.left, A, B); TreeNode right = lowestCommonAncestor(root.right, A, B); if (left != null && right != null) { return root; } if (left != null) { return left; } if (right != null) { return right; } return null; } }

    原题链接点这里

    鸣谢

    非常感谢你愿意花时间阅读本文章,本人水平有限,如果有什么说的不对的地方,请指正。 欢迎各位留言讨论,希望小伙伴们都能每天进步一点点。

    Processed: 0.011, SQL: 8