Post-order traversal recursive solution in C++


  • 0
    D

    What we need to do here is to do post-order traversal and the visit function is to check whether root is p or q. In the following code, once we find p or q, we reset p or q to nullptr to indicate that p or q is found.
    If both p and q are found in a left subtree, then just return the root (when p and q are both found at the first time). If p and q are found in different subtrees of root, then return root. If both p and q are both found in a right subtree, return the root when they are found first time .

    class Solution {
    private:
        TreeNode* dfs(TreeNode* root, TreeNode* &p, TreeNode* &q)
        {
            bool retRoot=false; // true means only one of p and q is found in the left subtree 
            if(!root) return root;
            TreeNode* res;
            res = dfs(root->left, p, q); // search the left subtree
            if(!p && !q) return res; // if found both p and q, return the root when they are found first time
            if (!p || !q) retRoot = true; // check if one of p and q is found in the left tree
            res = dfs(root->right, p, q); // search the right subtree
            if(!p && !q)  // if we found both p and q
                return  retRoot?root:res; // if one is in the left subtree and the other is in the right subtree, return root, otherwise both of them are in the right subtree, so return the root when they first time are found
            if(root==p) p =nullptr;  // check whether root is p or q
            else if (root==q) q=nullptr;
            return root;
        }
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            return dfs(root, p, q);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.