算法-最近公共祖先

236. 二叉树的最近公共祖先
首先，什么是最近公共祖先，这个要搞清楚

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;
        else if(left==null) 
            return right;
        else if(right==null) 
            return left;
        else
            return null; //本颗子树上没有
    }
}

添加链接描述

很明显利用bst的性质

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q){
            return root;`在这里插入代码片`
        }
        if(p.valroot.val && q.val>root.val){
            return lowestCommonAncestor(root.right,p,q);
        }else { //必然是分列左右
            return root;
        }
    }
}

添加链接描述
先找到p和q的最近公共祖先f，然后分别计算pq到f的距离

class Solution {
    int disQ,disP;
    public int findDistance(TreeNode root, int p, int q) {
        TreeNode lowestFather=getLowsetF(root,p,q);
        getDis(lowestFather,p,q,0);
        return disP+disQ;
    }

    private void getDis(TreeNode node, int p, int q, int dis) {
        if (node==null){
            return;
        }
        if (node.val==p){
            disP=dis;
        }
        if (node.val==q){
            disQ=dis;
        }
        if (disQ!=0 && disP!=0){
            return;
        }
        getDis(node.left,p,q,dis+1);
        getDis(node.right,p,q,dis+1);
    }

    private TreeNode getLowsetF(TreeNode root, int p, int q) {
        if (root==null){
            return null;
        }
        if (root.val==p || root.val==q){
            return root;
        }
        TreeNode left=getLowsetF(root.left,p,q);
        TreeNode right=getLowsetF(root.right,p,q);
        if (left!=null && right!=null){
            return root;
        }else if (left==null){
            return right;
        }else if (right==null){
            return left;
        }else {
            return null;
        }
    }
}