力扣 236 二叉树的最近公共祖先

题意：给定一个二叉树和两个节点，找到两个节点的最近公共祖先

思路：后续遍历树，可见注释

思想：后跟遍历

复杂度：时间O（n)，空间O(n)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root, p, q);
    }
    
    TreeNode find(TreeNode root, TreeNode p, TreeNode q) {
        // 根节点是null，直接返回 
        if(root == null)
            return null;
        // 跟节点是p或者q直接返回该节点
        if(root == p || root == q)
            return root;
        // 递归的在左右子树中找p和q
        TreeNode l = find(root.left,p,q);
        TreeNode r = find(root.right,p,q);
        // 当在左右子树中都找到节点时，返回root
        if(l != null && r != null)
            return root;
        // 当左子树或右子树不为空时返回左右子树节点
        if(l != null)
            return l;
        if(r != null)
            return r;
        // 默认情况返回null
        return null;
    }
}