leetcode 236. Lowest Common Ancestor of a Binary Tree

以你之姓@ 2022-07-25 16:47 157阅读 0赞

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).”

_______3______
           /              \
        ___5__          ___1__
       /      \        /      \
       6      _2       0       8
             /  \
             7   4

For example, the lowest common ancestor (LCA) of nodes `5` and `1` is `3`. Another example is LCA of nodes `5` and `4` is `5`, since a node can be a descendant of itself according to the LCA definition.

第一种方法

struct TreeNode {  
        int val;  
        TreeNode *left;  
        TreeNode *right;  
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
    };  
      
    class Solution {  
          
        void findpath(TreeNode* node, TreeNode* p,vector<TreeNode*>pathpp,vector<TreeNode*>&pathp)  
        {  
            if(node==p)  
            {  
                vector<TreeNode*>path=pathpp;  
                path.push_back(node);  
                pathp=path;  
                return ;  
            }  
            if(node->left!=NULL)  
            {  
                vector<TreeNode*>path=pathpp;  
                path.push_back(node);  
                if(node->left==p)  
                {  
                    path.push_back(p);  
                    pathp=path;  
                    return ;  
                }  
                else  
                    findpath(node->left,p,path,pathp);  
            }  
            if(node->right!=NULL)  
            {  
                vector<TreeNode*>path=pathpp;  
                path.push_back(node);  
                if(node->right==p)  
                    {  
                        path.push_back(p);  
                        pathp=path;  
                    return ;  
                }  
                else  
                    findpath(node->right,p,path,pathp);  
            }  
        }  
    public:  
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  
            vector<TreeNode*>pathp,pp,qq,pathq;  
            findpath(root,p,pp,pathp);  
            findpath(root,q,qq,pathq);  
            int k=pathp.size()<pathq.size()?pathp.size():pathq.size();  
            int i=0;  
            while(i<k&&pathp[i]==pathq[i])  
                i++;  
            if(i==k)  
                return pathp.size()<pathq.size()?pathp.back():pathq.back();  
            else  
                return pathp[i-1];  
        }  
    };

Memory Limit Exceeded

构造节点TN记录每个节点的父节点，否则向上找父节点太麻烦，val其实也可以不要。

struct TN {
    	int val;
    	TN*parent;
    	TN(int x) : val(x),parent(NULL) {}
    };
    class Solution {
    public:
    	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    		vector<TreeNode*>que, qq;
    		que.push_back(root);
    		TN*root1 = new TN(root->val);
    		vector<TN*>que1, qq1; que1.push_back(root1);
    		bool pf(true), qf(true);
    		while (!que.empty()&&(pf||qf))
    		{
    			vector<TreeNode*>newque;
    			vector<TN*>newque1;
    			for (int i = 0; (i < que.size()) && (pf || qf); i++)
    			{
    				if (que[i] == p)
    					pf = false;
    				if (que[i] == q)
    					qf = false;
    				qq.push_back(que[i]);
    				qq1.push_back(que1[i]);
    				if (que[i]->left != NULL)
    				{
    					TN*n = new TN(que[i]->left->val);
    					n->parent = que1[i];
    					newque.push_back(que[i]->left);
    					newque1.push_back(n);
    				}
    				if (que[i]->right != NULL)
    				{
    					TN*n = new TN(que[i]->right->val);
    					n->parent = que1[i];
    					newque.push_back(que[i]->right);
    					newque1.push_back(n);
    				}
    			}
    			que = newque;
    			que1 = newque1;
    		}
    		int pindex = find(qq.begin(), qq.end(), p) - qq.begin();
    		int qindex = find(qq.begin(), qq.end(), q) - qq.begin();
    		vector<TN*>pathp, pathq;
    		TN*nn = qq1[pindex];
    		while (nn!= NULL)
    		{
    			pathp.push_back(nn);
    			nn = nn->parent;
    		}
    		nn = qq1[qindex];
    		while (nn != NULL)
    		{
    			pathq.push_back(nn);
    			nn = nn->parent;
    		}
    		int k = pathp.size()<pathq.size() ? pathp.size() : pathq.size();
    		int i = 0;
    		while (i<k&&pathp[pathp.size() - 1 - i] == pathq[pathq.size()-1-i])
    			i++;
    		if (i == k)
    		{
    			TN*tt = pathp.size() < pathq.size() ? pathp[0] : pathq[0];
    			int reindex = find(qq1.begin(), qq1.end(), tt) - qq1.begin();
    			return qq[reindex];
    		}
    		else
    		{
    			TN*tt = pathp[pathp.size() - i];
    			int reindex = find(qq1.begin(), qq1.end(), tt) - qq1.begin();
    			return qq[reindex];
    		}
    	}
    };

accepted

[definition of LCA on Wikipedia]: https://en.wikipedia.org/wiki/Lowest_common_ancestor