236. 二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的
深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

tips

树中一个节点的祖先,是指从祖先节点出发,能够到达这个节点,公共祖先是指从这个祖先节点出发,既能到达这个节点,又能到达另一个节点,而最近公共祖先就是指这两个节点的所有祖先中离的最近的,也即最近公共祖先节点满足一个节点在它的左子树上,另一个节点在它的右子树上

解法1

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if(!root || !p || !q)
    		return nullptr;
    	vector<TreeNode *> path1;
        if(!findPath(root,path1,p))
        	return nullptr;
    	vector<TreeNode *> path2;
    	if(!findPath(root,path2,q))
    		return nullptr;
    	return getIntersectionNode(path1,path2);       
    }

    bool findPath(TreeNode *root,vector<TreeNode *> &path,TreeNode *target)
    {
    	if(root == nullptr)
    		return false;
    	if(root == target)//从底往上层次递进讨论
    	{
    		path.push_back(root);
    		return true;
    	}
    	path.push_back(root);
    	if(findPath(root->left,path,target))
    		return true;
    	if(findPath(root->right,path,target))
    		return true;
    	path.pop_back();//恢复函数参数刚传进来时的状态
    	return false;

    }

    TreeNode *getIntersectionNode1(vector<TreeNode *> &path1, vector<TreeNode *> &path2) {

    	int num1 = path1.size();
    	int num2 = path2.size();
    	int index1 = num1-1;
    	int index2 = num2-1;
    	int diff = abs(num1-num2);
    	if(num1 < num2)
    		index2 = index2-diff;
    	else
    		index1 = index1-diff;
    	if(path1[index1] == path2[index2])
    		return path1[index1];
        //这种方法是从后向前找两个路径上第一个这样的前一个节点:这两个前一个节点相等
    	while(index1)//至多循环进行到下标为1时截止
    	{
    		if(path1[index1-1] == path2[index2-1])
    			return path1[index1-1];
    		else
    		{
    			index1 = index1-1;
    			index2 = index2-1;
    		}
    	}
    	return nullptr;        
    }

    TreeNode *getIntersectionNode2(vector<TreeNode *> &path1, vector<TreeNode *> &path2) {

    	int num1 = path1.size();
    	int num2 = path2.size();
    	int n = min(num1,num2);
    	int index = 0;
        //从前往后找第一个这样的节点:它的在两个路径上的next节点不相等
    	for(;index < n-1;index++)
    	{
    		if(path1[index+1]!=path2[index+1])
    			return path1[index];
    	}
    	return path1[index];       
    }
};

解法2

这个方法主要的一点是这个递归函数的返回值有多重的含义,正常的情况是遍历树寻找p或者q,中间进行了一些处理,当满足一些条件时,能返回最近公共祖先。这个解法利用了最近公共祖先的一个性质:一个节点是最近公共祖先,那么它的左子树一定包含一个节点p,它的右子树一定包含另一个节点q;节点p和q是不同的,p不可能既在左子树又在右子树。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if(root == nullptr)
            return nullptr;
        if(root == p || root == q)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != nullptr && right != nullptr) 
            return root;
        else if(left != nullptr) 
            return left;
        else if(right != nullptr) 
            return right;
        else 
            return nullptr;
    }
};

236. 二叉树的最近公共祖先

上一篇:cpp库的编写


下一篇:Header响应头 详解