LeetCode Lowest Common Ancestor

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root -> left, p, q);
        TreeNode* right = lowestCommonAncestor(root -> right, p, q);
        return !left ? right : (!right ? left : root);
    }

遇到p和q直接返回之，避免了开辟空间记录是否出现过p和q的问题（根据返回值是NULL还是p和q区分）。

low的方法：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return NULL;
        TreeNode* res = NULL;
        dfs(root, p, q, res);
        return res;
    }
    vector<int> dfs(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& res) {
        vector<int> ret(2, 0), leftsub(2,0), rightsub(2,0);
        if(res) return ret;
        if(root -> left == root -> right){
            if(root == p) ret[0]++;
            if(root == q) ret[1]++;
            return ret;
        }
        if(root -> left){
            leftsub = dfs(root -> left, p, q, res);
        }
        if(root -> right){
            rightsub = dfs(root -> right, p, q, res);
        }
        ret[0] = leftsub[0] || rightsub[0] || (root == p);
        ret[1] = leftsub[1] || rightsub[1] || (root == q);
        if(res == NULL && ret[0] == 1 && ret[1] == 1) res = root;
        return ret;
    }