房地产网站建设策划方案,国外做蛋糕的网站,惠州市网站设计公司,制作微信网站模板思路#xff1a;递归三部曲
第一步#xff1a;确定参数和返回值
题目要求找到指定的结点#xff0c;就需要返回结点。
题目又涉及到p,q就需要传入p,q#xff0c;需要遍历传入root
第二步#xff1a;确定终止条件
当遍历到结点为空说明到底没找到返回空
或者遍历到p,… 思路递归三部曲
第一步确定参数和返回值
题目要求找到指定的结点就需要返回结点。
题目又涉及到p,q就需要传入p,q需要遍历传入root
第二步确定终止条件
当遍历到结点为空说明到底没找到返回空
或者遍历到p,q目标结点返回目标结点
第三步确定单层逻辑
首先要找到最近公共结点和pq有什么特别关系
一种情况就是pq在root的左右子树上
最近祖先就是当left和right都不为空时
二种情况就是pq本身就是最近公共祖先p/q在左右子树上
这种情况遍历到的第一个目标p/q就是题目所要的最近公共祖先返回即可
其他所有的结点都是null即不是目标结点直接将搜索到的第一个p/q不是null的结点一路返回
class Solution {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);if(left null right null){return null;}if(left ! null right ! null){return root;}if(left ! null){return left;}if(right ! null){return right;}return root;}
}
