昆明做网站的网络公司广州公共资源交易中心官网

二叉树的最近公共祖先

找p和q就行，找不到p和q的节点就返回null，找到的就层层返回p或q，其他的还是返回null。直到某一层的left和right都不为null说明得到了最近公共节点，再将这个节点层层返回。如果p和q存在祖先和子节点的关系，就层层返回祖先。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);// 左右子树均没有p和q，直接返回nullif (left == null && right == null) {return null;}// 左子树返回null，右子树中存在p或q，也可能存在p和qif (left == null) {return right;}// 右子树返回null，左子树中存在p或q，也可能存在p和qif (right == null) {return left;}// p和q分列两个子树中，root是最近公共祖先return root;
}

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤
个人主页：星不易 ❤
算法通关村专栏：不易|算法通关村 ❤