在二叉樹中找到兩個結點的最近公共祖先(LCA) Apare_xzc

在二叉樹中找到兩個結點的最近公共祖先(LCA)

牛客題目連結<–

樹的結點定義：

struct TreeNode{
	int val;
	struct TreeNode * left;
	struct TreeNode * right;
	TreeNode(int x=0) : val(x), left(NULL), right(NULL) {}
}
           

題意：

給定一顆二叉樹的根結點，資料保證樹中每個結點的val值都不同。給兩個值O1, O2， 求O1所在結點 和 O2 所在結點 的最近公共祖先結點的val值。

函數接口要求：

/*
* struct TreeNode{
* 	int val;
* 	struct TreeNode * left;
* 	struct TreeNode * right;
*	TreeNode(int x=0) : val(x), left(NULL), right(NULL) {}
* }
*/
class Solution {
public:
    /**
     * 
     * @param root TreeNode類 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root,int o1,int o2) {
    	//write code here
	}
};
           

思路一：dfs找到所有O1的祖先結點，dfs找到所有O2的祖先結點，然後bfs層序周遊，找到最後一個即為O1祖先，有為O2祖先 的結點即為答案

class Solution {
public:
    /**
     * 
     * @param root TreeNode類 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    void dfs(TreeNode * now,int val,unordered_map<TreeNode*,int>& mp) {
        if(!now) return;
        if(now->val==val) { //找到了這個值 
            mp[now] = 1;
            return;
        }
        if(now->left) {
            dfs(now->left,val,mp);
            auto it = mp.find(now->left);
            if(it!=mp.end()) { //說明在左子樹中 
                mp[now] = 1;
                return;
            }
        }
        if(now->right) {
            dfs(now->right,val,mp);
            auto it = mp.find(now->right);
            if(it!=mp.end()) {
                mp[now]=1;
            }
        }
    }                    
    int bfs(TreeNode * root,unordered_map<TreeNode*,int>&fo1,unordered_map<TreeNode*,int>&fo2) {
        if(!root) return -1; 
        queue<TreeNode*> Q;
        Q.push(root);
        int ans = -1;
        while(!Q.empty()) {
            TreeNode * tp = Q.front();
            Q.pop();
            if(fo1.find(tp)!=fo1.end() && fo2.find(tp)!=fo2.end()) ans = tp->val;
            if(tp->left) Q.push(tp->left);
            if(tp->right) Q.push(tp->right);
        }
        return ans;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        unordered_map<TreeNode*,int> fo1; //标記所有o1的祖先結點(包括它自己)
        unordered_map<TreeNode*,int> fo2; //标記所有o2的祖先結點(包括它自己)
        dfs(root,o1,fo1);
        dfs(root,o2,fo2);
        return bfs(root,fo1,fo2); 
    }
};
           

思路二：樸素倍增。找到o1的高度和o2的高度，先跳到高度一樣了，然後再一起一個一個往上跳，直到相遇

class Solution {
public:
    /**
     * 
     * @param root TreeNode類 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root,int o1,int o2) {
    	unordered_map<int,int> Height;
    	unordered_map<int,int> fa;
    	getFatherAndHeight(root,1,Height,fa);
    	int h1 = Height[o1], h2 = Height[o2];
    	while(h2>h1) o2 = fa[o2],--h2;
    	while(h2<h1) o1 = fa[o1],--h1;
		while(o2!=o1) o2 = fa[o2], o1 = fa[o1];
		return o1; 
	}
    void getFatherAndHeight(TreeNode * root,int h,unordered_map<int,int>&Height,unordered_map<int,int>& fa) {
    	if(!root) return;
    	Height[root->val] = h;
    	if(root->left) {
    		fa[root->left->val] = root->val;
    		getFatherAndHeight(root->left,h+1,Height,fa);
		}
		if(root->right) {
			fa[root->right->val] = root->val;
			getFatherAndHeight(root->right,h+1,Height,fa);
		}
	} 
};
           

思路三，遞歸

//201ms
class Solution {
public:
    /**
     * 
     * @param root TreeNode類 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
     
     TreeNode* dfs(TreeNode * root,int o1,int o2) {
         if(root==nullptr||root->val==o1||root->val==o2) return root;
         TreeNode * lans = dfs(root->left,o1,o2); 
         TreeNode * rans = dfs(root->right,o1,o2);
         if(lans==nullptr) return rans; //o1,o2都在右子樹
         if(rans==nullptr) return lans; //o1,o2都在左子樹
         return root; //o1，o2，左子樹右子樹各有一個
     }
     int lowestCommonAncestor(TreeNode* root,int o1,int o2) {
    	return dfs(root,o1,o2)->val; 
	}
 
};
           

自己調試代碼

/*struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x):val(x),left(NULL),right(NULL){}
	TreeNode():left(NULL),right(NULL){} 
};*/
vector<string> vstr = {"1","2","4","#","#","5","#","#","3","6","#","#","7","#","#"}; //先序建樹 
TreeNode * build(vector<string>& vstr,int& x) {
	if(vstr[x]==string("#")) {
		++x; return nullptr;		
	}  
	TreeNode * root = new TreeNode();
	istringstream ism(vstr[x++]);
	ism>>root->val;
	root->left = build(vstr,x);
	root->right = build(vstr,x);
	return root; 
}