在二叉树中找到两个节点的最近公共祖先

 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     思路很简单，我们可以采用递归函数来解决，我们每访问一个结点，我们以该结点为出发点，默认
     两个目标还没有找到。根据当前结点查找左子节点、右子节点、自身结点。然后根据查找结果再将
     结果返回给上层结点进行更新自身的查找结果。
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        if(root->val==o1||root->val==o2){
            return NULL;
        }
        // write code here
        bool findo1=false;
        bool findo2=false;
        int nearest_root = root_first(root, o1, o2,findo1,findo2);
        return nearest_root;      
    }
    int root_first(TreeNode* root,int o1,int o2,bool& findo1,bool& findo2 )
    {
        /*
        传入的findo1为引用，可以更新父结点的查找结果。
        if(root->val==o1&&!findo1){
            findo1=true;
        }
        if(root->val==o2&&!findo2){
            findo2=true;
        }
        if(findo1&&findo2){
            return NULL;
        }
        */
        int res_left = NULL;
        int res_right = NULL; 
        bool findo1_=false;
        bool findo2_ = false;
           if(root->left){           
           res_left = root_first(root->left, o1, o2,findo1_,findo2_);
           if(!findo1){
                findo1=findo1_;
            }
            if(!findo2){
                findo2=findo2_;
            }
           }    
        if(!findo1_||!findo2_){
            if(root->right){
             res_right = root_first(root->right, o1, o2,findo1_,findo2_);
               if(!findo1){
                findo1=findo1_;
            }
            if(!findo2){
                findo2=findo2_;
            }
            }
        }else{
            return res_left;
        }
        if(findo1_&&findo2_){
           if(res_right==NULL){
               return root->val;
           }else{
               return res_right;
           }         
        }else{
        if(root->val==o1&&!findo1){
            findo1_=true;
            findo1 = true;
        }
        if(root->val==o2&&!findo2){
            findo2_=true;
            findo2=true;
        }
        if(findo1_&&findo2_){
            return root->val;
        }
            return NULL;
        }
    }
};

  public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root==null) return -1;
        if(o1==root.val || o2==root.val) return root.val;
        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right,o1,o2);
        if(left ==-1) return right;
        if(right ==-1)  return left;
        return root.val;
    }

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        if (root == nullptr) return -1;
        if (root->val == o1 || root->val == o2) return root->val;
        
        int left = lowestCommonAncestor(root->left, o1, o2);
        int right = lowestCommonAncestor(root->right, o1, o2);
        
        if (left != -1 && right != -1) return root->val;
        else if (left != -1) return left;
        else if (right != -1) return right;
        else return -1;
    }
};

来个通俗易懂的解法（非递归）：
1.分别采用非递归后序遍历找到要寻找的节点o1，o2，并且返回遍历栈s1,s2
2.遍历栈中s1,s2从前往后数，最后一个相同的节点就是最近的公共祖先
3.由于栈是先进后出，因此需要把栈内的元素放到队列中，放到队列中挨个数即可。

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        stack s1 = postOrder(root,  o1);
        stack s2 = postOrder(root,  o2);
        vector v1,v2;
        int res;
        queue q1,q2;
        TreeNode* p;
        int size1 = s1.size();
        int size2 = s2.size();
        while(!s1.empty()){
            p = s1.top();
            q1.push(p);
            s1.pop();
        }
        while(!s2.empty()){
            p = s2.top();
            q2.push(p);
            s2.pop();
        }
        queue deleteQueue= size1>size2?q1:q2;
         queue saveQueue = size1>size2?q2:q1;
        for(int i =0;i<abs(size1-size2);++i){
            deleteQueue.pop();
        }
        int r1,r2;
        while(!deleteQueue.empty()&&!saveQueue.empty()){
             r1 =saveQueue.front()->val;
             r2 =deleteQueue.front()->val;
            if(r1==r2){return r1;}
             deleteQueue.pop();
             saveQueue.pop();

        }
        return 0;
    }
      stack postOrder(TreeNode* root,int num){
        stack nodeStack;
        TreeNode * pointer = root;
        TreeNode * pre = root;
        while(pointer != nullptr){
            while(pointer -> left != nullptr){
                nodeStack.push(pointer);
                pointer = pointer -> left;
            }
            while(pointer != nullptr && (pointer -> right == nullptr ||pre == pointer->right)){
                if(num==pointer->val){
                    nodeStack.push(pointer);
                    return nodeStack;
                }
                pre = pointer;
                pointer = nodeStack.top();
                nodeStack.pop();
            }
            nodeStack.push(pointer);
            pointer = pointer -> right;
        }
        return nodeStack;
    }

};

public class Solution {
//用来记录树中所有节点对应的的父节点
    HashMap<Integer, Integer> map = new HashMap<>();
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        List<Integer> list = new ArrayList<>();
        dfs(root);
        list.add(o1);
        int val1 = map.get(o1);
        while(map.get(val1) != null){
            val1 = map.get(val1);
            list.add(val1);
        }
        if(list.contains(o2)){
            return o2;
        }
        while(map.get(o2) != null){
             o2 = map.get(o2);
             if(list.contains(o2)){
                return o2;
            }
        }
        return -1;
    }
    
    public void dfs(TreeNode root){
        if(root.left != null){
            map.put(root.left.val, root.val);
            dfs(root.left);
        }
        if(root.right != null){
            map.put(root.right.val, root.val);
            dfs(root.right);
        }
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return process(root, o1, o2).ans.val;
    }
    
    public Info process(TreeNode node, int o1, int o2) {
        if (node == null) {
            return new Info(null, false, false);
        }
        Info leftInfo = process(node.left, o1, o2);
        Info rightInfo = process(node.right, o1, o2);
        TreeNode ans = null;
        boolean findP = o1 == node.val || leftInfo.findP || rightInfo.findP;
        boolean findQ = o2 == node.val || leftInfo.findQ || rightInfo.findQ;
        if (leftInfo.ans != null) {
            ans = leftInfo.ans;
        }
        if (rightInfo.ans != null) {
            ans = rightInfo.ans;
        }
        if (ans == null) {
            if (findP && findQ) {
                ans = node;
            }
        }
        return new Info(ans, findP, findQ);
    }
    
    class Info {
        TreeNode ans;
        boolean findP;
        boolean findQ;
        
        Info (TreeNode ans, boolean findP, boolean findQ) {
            this.ans = ans;
            this.findP = findP;
            this.findQ = findQ;
        }
    }
}

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root.val == o1 || root.val == o2){
            return root.val;
        }
        TreeNode treeNode = order(root, o1, o2);
        return treeNode.val;
    }
    public TreeNode order(TreeNode root, int o1, int o2){
        if(root == null)
            return null;
        if(root.val == o1 || root.val == o2)
            return root;
        TreeNode left = order(root.left, o1, o2);
        TreeNode right = order(root.right, o1, o2);
        
        if(left != null && right != null)
            return root;
        if(left == null && right == null)
            return null;
        
        return left == null? right: left;
    }

class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        '''
        思路很简单,遇到这种题一定要想简单思路。
        我们定义子树或本身中包含o1或o2的节点为公共节点。距离根最远的公共节点就是我们要求的最近公共祖先。
        1. 如果当前节点是第一个包含o1或o2的节点，那么当前节点一定是公共节点，但不一定是最近公共祖先，直接将其向上回溯即可
        2.否则就去看该节点的左右子树里找
            若左子树里找到了公共节点且右边没有，那就将左边找到的公共节点向上回溯
            若右子树里找到了公共节点且左边没有，那就将右边找到的公共节点向上回溯
            若左右子树中都有公共节点，那说明当前根是最近公共祖先，将其向上返回即可。
        '''
        
        def dfs(root,o1,o2):
            if not root&nbs***bsp;root.val == o1&nbs***bsp;root.val == o2:
                return root
            left = dfs(root.left,o1,o2)
            if not left:return dfs(root.right,o1,o2)
            right = dfs(root.right,o1,o2)
            if not right:return left
            return root
        return dfs(root,o1,o2).val 

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        TreeNode res = dfs(root, o1, o2);
        return res.val;
    }
    public TreeNode dfs(TreeNode root, int o1, int o2) {
        if(root == null || root.val == o1 || root.val == o2) {
            return root;
        }
        TreeNode left = dfs(root.left, o1, o2);
        TreeNode right = dfs(root.right, o1, o2);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}

class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        return self.dfs(root, o1, o2).val
    
    def dfs(self, root, o1, o2):
        if not root or root.val == o1 or root.val == o2:
            return root
        
        left = self.dfs(root.left, o1, o2)
        right = self.dfs(root.right, o1, o2)
        if left is None:
            return right
        if right is None:
            return left
        
        return root