[数据结构与算法]【剑指 Offer】68 - II. 二叉树的最近公共祖先(详细解析)

第 19 日： 二叉树的最近公共祖先

题目链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

题目

解题

1. 后序遍历

   解题思路：
   想了好久才有思路，我太难了；
   
   1后序遍历，找到结点（q或p）返回此结点
   2.在回溯的时候如果发现两边子树都有返回值（不为空），则返回此结点；另一种回溯的情况是只有一边子树又返回值，而当前结点与p或q相同，则返回此节点（因为这样就算是公共祖先为本身结点了）

   详细代码如下：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        
        TreeNode l=lowestCommonAncestor(root.left,p,q);
        TreeNode r=lowestCommonAncestor(root.right,p,q);
        if(l!=null&&r!=null) return root;
        
        if(root==p||root==q) return root;
        

        if(l!=null) return l;
        else 
        	if(r!=null) return r;
       
        return null;
    }
}