LeetCode 236. Lowest Common Ancestor of a Binary Tree(二叉树的最近公共祖先)
题目
分析
思路:寻找给定节点的公共祖先,一般这类题目可以采用树的遍历的思想来解决,在遍历树的过程中,我们可以找到这两个节点的位置,同时,在遍历的过程中,也可以知道到达节点的路径,当我们得到了路径,就可以找到两条路径的重叠的部分,那么两条路径开始分开的那个节点,就是所求的公共祖先节点,它的深度最大。
实现步骤:
1、递归:使用递归的思想可以完成二叉树的遍历。这里采用的是中根遍历的思想。为了确定路径,用0和1表示的字符串来实现路径的记录,规定向左字符串累加“1”,向右累加“0”,每当找到匹配节点,就把字符串值保存下来。这里用两个String类型的string1和string2来接收。这里的递归是判断左(右)子树是否存在,如果存在就把当前节点作为根节点,修改str并继续调用这个方法,最终遍历到叶子结点,没有左右子树,它也就是递归的终点。
/**
* 中根遍历
* @param root
*/
public void read(TreeNode root, TreeNode p, TreeNode q,String str){
if(root.left!=null){
read(root.left,p,q,str+"1");
}
if(root==p){
string1=str;
}else if(root==q){
string2=str;
}
if(root.right!=null){
read(root.right,p,q,str+"0");
}
}
2、得到了路径,下一步就是找到路径的重复部分,根据重复的部分找到那个最近的公共祖先并返回。
for(int i=0;i<((string1.length()>string2.length())?string2.length():string1.length());i++){
if(string1.charAt(i)==string2.charAt(i)){
if(string1.charAt(i)=='1'){
root=root.left;
}else{
root=root.right;
}
}else{
break;
}
}
return root;
完整代码:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
String string1="";
String string2="";
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
read(root, p, q, "");
for(int i=0;i<((string1.length()>string2.length())?string2.length():string1.length());i++){
if(string1.charAt(i)==string2.charAt(i)){
if(string1.charAt(i)=='1'){
root=root.left;
}else{
root=root.right;
}
}else{
break;
}
}
return root;
}
/**
* 中根遍历
* @param root
*/
public void read(TreeNode root, TreeNode p, TreeNode q,String str){
if(root.left!=null){
read(root.left,p,q,str+"1");
}
if(root==p){
string1=str;
}else if(root==q){
string2=str;
}
if(root.right!=null){
read(root.right,p,q,str+"0");
}
}
}