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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/*使用后续遍历，通过变量a，b标识是否访问过o1，o2，并且一直向上传递
当t结点的子树一边存在o1，一边存在o2则t为最小公共结点
特殊情况是，当该节点等于o1或o2，此时当其子节点中有等于另一个值的结点，则此节点即为最小公共结点
*/
#include <algorithm>
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(struct TreeNode* root, int o1, int o2) {
        // write code here
        struct TreeNode* p;
        int a=0;
        int b=0;
        findZ(root,&p,a,b,o1,o2);
        return p->val;
    }
    void findZ(TreeNode* root,struct TreeNode** fh,int& a,int &b,int o1, int o2){
        if(root)
        {
            int a1=0;
            int a2=0;
            int b1=0;
            int b2=0;
            findZ(root->left, fh,a1,b1,o1,o2);
            findZ(root->right,fh,a2,b2,o1,o2);                                                 
            if(root->val==o1)
            {
                a=1;
                if(b1||b2)
                    *fh=root;
            }
            a=a||a1||a2;
            if(root->val==o2)
            {
                b=1;
                if(a1||a2)
                    *fh=root;
            }
            b=b||b1||b2;
            if(a1!=a2&&b1!=b2&&a1!=b1){
                *fh=root;
            }
        }
    }
};