Share my C++ solution, works not only in BST, using DFS


  • 0
    X
    class Solution {
    public:
    	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    		if(!root) return NULL;
    		vector<TreeNode*> L1, L2;
    		bool find1 = false, find2 = false;
    		dfs(root, p, L1, find1);
    		dfs(root, q, L2, find2);
    
    	for(int i = 0; i < L1.size() && i < L2.size(); i++){
    		if(L1[i] != L2[i]){
    			return L1[i - 1];
    		}
    		if(i == L1.size() - 1)
    			return L1[i];
    		if(i == L2.size() - 1)
    			return L2[i];
    	}
    }
    
    void dfs(TreeNode* curr, TreeNode* target, vector<TreeNode*>& L, bool& find){
    	if(curr == target)
    	{
    		L.push_back(curr);
    		find = true;
    		return;
    	}
    
    	if(curr->left && !find){
    		L.push_back(curr);
    		dfs(curr->left, target, L, find);
    		if(!find)
    			L.pop_back();
    	}
    	
    
    	if(curr->right && !find){
    		L.push_back(curr);
    		dfs(curr->right, target, L, find);
    		if(!find)
    			L.pop_back();
    	}
    }
    };

  • 0
    G

    good my brother
    I just want to use dfs to solve
    but get a little problem
    thanks for your solution


Log in to reply
 

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