美丽乡村建设网站php源码,高质量的中山网站建设,域名解析怎么弄,建设工程类的网站问题描述#xff1a;
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大#xff08;一个…问题描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。 题目描述
解题思路
注意此题的前置条件是一定有公共祖先所以可以先判断当前节点是不是祖先如果是则继续往下找左右子树如果左右子树中有一边找到的公共祖先不存在直接返回另一边子树中的查找结果否则返回当前根节点
代码实现
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 1. 先看根节点是不是祖先if (root null || root p || root q) {return root;}// 2. 如果根节点是祖先有没有更近的祖先呢// 看看左子树TreeNode left lowestCommonAncestor(root.left, p, q);// 看看右子树TreeNode right lowestCommonAncestor(root.right, p, q);// 3. 如果有的话显然只会在一侧 判断一下if (left null) {return right;}if (right null) {return left;}// 4. 如果没有更近的默认还是返回rootreturn root;}
