力扣236 补9.14

做不来，我做中等题基本上都是没有思路，这里需要先遍历祖先节点，那必然用先序遍历，这题还是官方题解容易理解，第二火的题解反而把我弄得脑袋昏昏的。

 

 

class Solution {

    TreeNode ans;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

       

        dfs(root,p,q);

        return ans;

    }

    boolean dfs(TreeNode root,TreeNode p, TreeNode q){

        // 判断该树有没有p或q节点，有则为true

        if(root==null) return false;

        boolean l=dfs(root.left,p,q);

        boolean r=dfs(root.right,p,q);

        if((root==p||root==q)&&l==false&&r==false){

            // 注意要有l==false&&r==false，防止遇到p或q直接退出函数，还要看其子树还有没有p或q。

            return true;

        }

        if((root==p||root==q)&&(l==true||r==true)){

            ans=root;

            return true;

        }else if((l==true&&r==true)){

            ans=root;

            return true;

        }else {

            return l||r;

        }

    }

}