[数据结构与算法]LeetCode236 二叉树的最近公共祖先

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

本题采用递归后序遍历即可。

首先明确递归边界，当root==null时直接返回null即可。

若是在递归过程中找到了p或者q，则返回这个结点。

然后就是递归调用函数了，先遍历了右子树，然后遍历左子树，此时定义的right和left可以认为是已经得出的结果。这个结果就是值为p和q的两个结点。如果left和right都不为空，那么直接返回此结点值作为结果即可。

如果left或right为空，则应返回他的另一子树。