Java solution by finding the path for each node


  • 2
    K

    Find the path for each node.
    Compare each path to find the LCA

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root==null) return null;
        if(p==null || q==null)  return null;
        ArrayList<TreeNode> p_path = new ArrayList<TreeNode>();
        ArrayList<TreeNode> q_path = new ArrayList<TreeNode>();
        findPath(root, p, p_path);
        findPath(root, q, q_path);
        int min_len = Math.min(p_path.size(), q_path.size());
        int LCA = 0;
        for(int i=0; i<min_len; i++){
            if(p_path.get(i)==q_path.get(i))
                LCA = i;
        }return p_path.get(LCA);
        
    }
    public static boolean findPath(TreeNode root, TreeNode n1, List<TreeNode> path){
    	if(root == null)
    		return false;
    	path.add(root);
    	if(root == n1)
    		return true;
    	if(findPath (root.left, n1, path) || findPath(root.right, n1, path))
    		return true;
    	path.remove(path.size() - 1);
    	return false;
    }

  • 0
    F

    I have the same idea with you

    class Solution {
    public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        // use the depth first algorithm to get the path of p and q
        vector<TreeNode*> p_path;
        getPath(root, p, p_path);
        vector<TreeNode*> q_path;
        getPath(root, q, q_path);
        
        vector<TreeNode*> common_path;
        TreeNode *low_comm = 0;
        int min_length = min(p_path.size(), q_path.size());
    
        for (int i = 0; i < min_length; i++){
            if (p_path[i] == q_path[i]){
                low_comm = p_path[i];
            }
            
            else break;
        }
        
        return low_comm;
        
    }
    
    // get the path of one node
    bool getPath(TreeNode* node, TreeNode *p, vector<TreeNode*>& node_path){
        
        if (node == NULL) return false;
        
        node_path.push_back(node);
        if (node == p) return true;
        
        if (getPath(node->left, p, node_path)|| getPath(node->right, p, node_path)) return true;
        
        node_path.pop_back();
        
        return false;
        
    }
    

    };


Log in to reply
 

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