本文探讨如何在二叉树中快速找到两个节点的最近公共双亲（Lowest Common Ancestor）。当树为二叉查找树时，利用其特性可以简化问题。文中提供代码实现，包括针对二叉查找树和一般二叉树的解决方案，并介绍了通过中序遍历来推导节点关系的思路。
二叉树中两个节点的最近公共双亲(Lowest Common Ancestor)是所有这两个节点的双亲节点中离根节点最远的节点，如果其中一个节点是另一个节点的双亲节点，那么符合这个定义的节点就是这个双亲节点，如何快速简单的找到任意的两个节点的最近公共双亲节点是这里要讨论的话题。
首先将这个问题具体化，如果给定的树是一棵二叉查找树，那么这棵树的某些性质就可以为我们所用了。先看代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val>p.val && root.val>q.val) return lowes
最低0.47元/天 解锁文章
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
