做普通网站公司,yy直播在线观看,湖北工程建设总承包有限公司网站,做薪酬调查有哪些网站题目连接#xff1a;236. 二叉树的最近公共祖先 - 力扣#xff08;LeetCode#xff09;
题目描述#xff1a; 思路分析#xff1a;
由题可知#xff0c;我们需要找到 p 和 q 两个二叉树的最近公共祖先节点#xff0c;首先我们分析一下#xff0c;这个最近公共祖先节点…题目连接236. 二叉树的最近公共祖先 - 力扣LeetCode
题目描述 思路分析
由题可知我们需要找到 p 和 q 两个二叉树的最近公共祖先节点首先我们分析一下这个最近公共祖先节点的可能情况。1、这个最近公共祖先节点既不是 p 也不是 q简单来说p 和 q 一个是某个节点的左子树另一个是该节点的右子树也就是示例一的情况。2、这个最近公共祖先节点是 p 或者 q也就是说p 是 q 的父节点或者 q 是 p 的父节点也就是示例二的情况。接下来我们详细分析一下编写代码的过程
1、判断 root、p、q 中是否存在空节点如果存在空节点则直接返回 null
2、判断 root 是否等于 p 或者 q如果相等则直接返回 root表示已经找到了一个节点
3、从左子树和右子树中接着寻找另一个节点
4、如果同时找到了两个树那么说明这两个树是从同一个节点分化出来的则直接返回 root如果说只有找到了一个树那么说明另一个树是这个树的子树则直接返回找到的那个结点就可以原因可以看下面的图片 代码示例
lass Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null || p null || q null) return null;if(root p || root q) return root;TreeNode retLeft lowestCommonAncestor(root.left,p,q);TreeNode retRight lowestCommonAncestor(root.right,p,q);if(retLeft ! null retRight ! null) {return root;}else if(retLeft ! null) {return retLeft;}else {return retRight;}}
}
