236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
递归
public TreeNode
lowestCommonAncestor(TreeNode root
, TreeNode p
, TreeNode q
) {
if (root
== null
) {
return root
;
}
if (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
;
} else if (left
!= null
) {
return left
;
} else if (right
!= null
) {
return right
;
}
return null
;
}
转化为链表最后一个公共节点
LinkedList
<TreeNode> path1
= new LinkedList<>();
LinkedList
<TreeNode> path2
= new LinkedList<>();
public TreeNode
lowestCommonAncestor(TreeNode root
, TreeNode p
, TreeNode q
) {
return GetLastCommomParent(root
, p
, q
);
}
public TreeNode
GetLastCommomParent(TreeNode root
, TreeNode p
, TreeNode q
){
if (root
==null
|| p
==null
|| q
==null
) return null
;
GetNodePath(root
, p
, path1
);
GetNodePath(root
, q
, path2
);
return GetLastCommomNode(path1
, path2
);
}
public boolean GetNodePath(TreeNode root
, TreeNode p
, LinkedList
<TreeNode> path
){
path
.add(root
);
if (root
==p
) return true;
boolean found
= false;
if (root
.left
!=null
&& !found
)
found
= GetNodePath(root
.left
, p
, path
);
if (root
.right
!=null
&& !found
)
found
= GetNodePath(root
.right
, p
, path
);
if (!found
)
path
.pollLast();
return found
;
}
public TreeNode
GetLastCommomNode(LinkedList
<TreeNode> path1
, LinkedList
<TreeNode> path2
){
Iterator
<TreeNode> iter1
= path1
.iterator();
Iterator
<TreeNode> iter2
= path2
.iterator();
TreeNode last
= null
;
while (iter1
.hasNext() && iter2
.hasNext()){
TreeNode a
= iter1
.next();
TreeNode b
= iter2
.next();
if (a
.val
==b
.val
)
last
= a
;
}
return last
;
}
