LeetCode 热题100-67-二叉树最近公共祖先

核心思想:后序遍历 思路： 最近任何两个节点都有两种情况： 1.signL == true && signR == true，signL这意味着节点左子树包含q或qp，同理signR；两者同时为true节点是公共祖先； 2.(root.val == p.val || root.val == q.val) && (signL == true || signR ==true)，这意味着该节点是q或p的节点之一q不在本节点的另一个节点在本节点的左子树或右子树中。 当上述两种情况之一得到满足时，它们是最近的公共祖先。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { 
            private TreeNode ans;      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
                boolean res = LRD(root, p, q);         if(res == true){ 
                    return ans;         }else{ 
                    return null;         }     }      public boolean LRD(TreeNode root, TreeNode p, TreeNode q){ 
                if(root == null){ 
                    return false;         }         boolean signL = LRD(root.left, p, q);         boolean signR = LRD(root.right, p, q);         if((signL == true && signR == true)||((root.val == p.val || root.val == q.val) && (signL == true || signR ==true))){ 
       
            ans = root;
        }
        //未找到最近祖先节点，则返回左右子树中为true的值或者本节点为p或者q
        return signL || signR || (root.val == p.val || root.val == q.val);
    }
}