Find the Deepest Roots, the Jedi's Quest
IntuitionHmm... The deepest nodes we must find, and their common ancestor identify. Like seeking the source of the dark side, to the roots we must travel.Approa
# Intuition
Hmm... The deepest nodes we must find, and their common ancestor identify. Like seeking the source of the dark side, to the roots we must travel.

# Approach
1. findv: Performs DFS to find a path to a target value (p or q), storing the path in ans and setting res=true if found.
2. FindValue: Locates a node with a specific value in the tree.
3. lowestCommonAncestor: Uses findv to get paths for p and q, then compares paths to find their last common node (LCA).
4. solve: Recursively finds all leaf nodes and their depths, storing them in ans.
5. subtreeWithAllDeepest:
    - Collects all deepest leaves using solve.
    - Finds their LCA by iteratively computing pairwise LCAs.

# Complexity
- Time complexity: $$O(n^2)$$

- Space complexity: $$O(n)$$

# Code
```cpp []
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void findv (TreeNode* root, int value, vector<int>&ans, bool &res){
        if (root==NULL||res){return;}
        ans.push_back(root->val);
        if (root->val==value){res=true;return;}
        findv(root->left,value,ans,res);
        findv(root->right,value,ans,res);
        if (!res){ans.pop_back();}
    }
    TreeNode* FindValue (TreeNode* root, int Value){
        if (root==NULL){return NULL;}
        if (root->val==Value){return root;}
        TreeNode* left=FindValue(root->left,Value);
        if (left){return left;}
        return FindValue(root->right,Value);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, int p, int q) {
        vector<int>ans1,ans2;
        bool res=false;
        findv(root,p,ans1,res);
        res=false;
        findv(root,q,ans2,res);
        int x=ans1[0],size=min(ans1.size(),ans2.size());
        for (int i=1;i<size;i++){if (ans1[i]==ans2[i]){x=ans1[i];}}
        return FindValue(root,x);
    }
    void solve(TreeNode* root, int d, vector<vector<int>>&ans){
        if (root==NULL){return;}
        if (root->left==NULL && root->right==NULL){
            ans.push_back({d,root->val});
        }
        solve(root->left,d+1,ans);
        solve(root->right,d+1,ans);
    }
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        if (root->left==NULL && root->right==NULL){return root;}
        vector<vector<int>>ans;
        vector<int>a;
        solve(root,0,ans);
        sort(ans.begin(),ans.end());
        int d=ans[ans.size()-1][0],s=0;
        for (int i=ans.size()-1;i>=0;i--){
            if (ans[i][0]==d){a.push_back(ans[i][1]);}
        }
        if (a.size()==1){return lowestCommonAncestor(root,a[0],a[0]);}
        TreeNode* op=lowestCommonAncestor(root,a[0],a[1]);
        while (a.size()>1){
            op=lowestCommonAncestor(root,a[a.size()-1],a[a.size()-2]);
            a.pop_back();
            a.pop_back();
            a.push_back(op->val);
        }
        return op;
    }
};
```
['C++']