保定建站模板,男女做的那些事情的网站,网站服务器租用价格表,重庆市建设工程信息网信用信息发布平台问题背景
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为#xff1a;对于有根树 T T T 的两个节点 p p p、 q q q#xff0c;最近公共祖先表示为一个节点 x x x#xff0c;满足 x x x 是 p p p、 q q q 的祖先且 x x x 的深度尽可能大…问题背景
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为对于有根树 T T T 的两个节点 p p p、 q q q最近公共祖先表示为一个节点 x x x满足 x x x 是 p p p、 q q q 的祖先且 x x x 的深度尽可能大一个节点也可以是它自己的祖先。
数据约束
树中节点数目在范围 [ 2 , 1 0 5 ] [2, 10 ^ 5] [2,105] 内。 − 1 0 9 ≤ N o d e . v a l ≤ 1 0 9 -10 ^ 9 \le Node.val \le 10 ^ 9 −109≤Node.val≤109所有 N o d e . v a l Node.val Node.val 互不相同 。 p ≤ q p \le q p≤q p p p 和 q q q 均存在于给定的二叉树中。
解题过程
首先要想明白一种情形如果递归到某个节点发现题中所要求的两个节点分别在这个节点的两棵子树中那么它就是答案由两个条件保证
这个节点以上往根节点的方向的节点不管是不是公共祖先都一定不满足 最近 这个要求。这个节点以下往子树的方向的节点必然不满足同时是两棵子树的根节点但是要求的两个节点分别在两棵子树上。这就意味着这些节点都不可能成为公共祖先。
在此基础上如果当前节点是题中要求的其中某一个节点那么它就是答案。 剩下的情况遇到空节点返回空是常规此操作递归的过程中只在左右子树上找到相应的节点那就只返回递归相应子树的结果如果在子树上都没有找到同样返回空。
具体实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
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 root;}// 返回递归子树时得到的非空的结果两者都为空时随便返回哪个都可以合并到 right 中return left ! null ? left : right;}
}
