网站建设 中企动力医院,wordpress子网页,苏州区建设局网站,创建团购网站二叉树的最近公共祖先
找p和q就行#xff0c;找不到p和q的节点就返回null#xff0c;找到的就层层返回p或q#xff0c;其他的还是返回null。直到某一层的left和right都不为null说明得到了最近公共节点#xff0c;再将这个节点层层返回。如果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;
}如果对您有帮助请点赞关注支持我谢谢❤ 如有错误或者不足之处敬请指正❤ 个人主页星不易 ❤ 算法通关村专栏不易|算法通关村 ❤
