leetcode刷题/二叉树 235. 二叉搜索树的最近公共祖先

题意:

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

解题思路:

这道题可以分两步走 问 答 第一步 分别在搜素树种找出p q节点的路径,然后存入要给数组 第二步 比较两个数组,返回最后一个相同的值即可. 小提示 无法得知当前哪个节点的路径比较短,所以可以用swap来确保第一个是短的那边,方便返回 大致过程为找两个路径,比较路径找到最近公共祖先返回即可

代码:

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

class Solution {
          
   
public:
    
//在搜素树寻找路径
void findWay(TreeNode *root, TreeNode *node, vector<TreeNode *> &path)
{
          
   
	path.push_back(root);
	if (root->val == node->val)
		return;
	else if (root->val > node->val)
		findWay(root->left, node, path);
	else
		findWay(root->right, node, path);
	return;
}

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
          
   
    //存储p节点的路径
    vector<TreeNode *>path_p;
	findWay(root, p, path_p);
    //存储q节点的路径
	vector<TreeNode *>path_q;
	findWay(root, q, path_q);
        
    //确保第一个路径是较短的一个
	if (path_p.size() > path_q.size())
		swap(path_p, path_q);
    //找最后一个相同的值返回
	for (int i = 0; i < path_p.size(); i++)
	{
          
   
		if (path_p[i] != path_q[i])
			return path_p[i - 1];
	}
    //如果短的一边没返回,说明是包含在长的里面,最近的公共祖先就是短的路径的最后一个节点
	return path_p.back();
    }
};

第二种

第一种思路比较清晰,但是需要遍历两次,还需比较数组.有点麻烦.可以做到一次遍历即可. 问 答 如何做到只遍历一次即可? 根据二叉树的特性,p q的公共祖先的值一定是夹在p q的值中间的节点 该如何完成? 如果 当前节点的值同时大于p q的值,就递归左节点.同时小于即递归右节点. 如果不是就说明这个节点就在p q值得中间!直接返回该节点即可. 思路就是判断当前值与 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) {}
 * };
 */

class Solution {
          
   
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
          
   
    //同时小于结点值
    if (root->val > p->val && root->val > q->val)
		return lowestCommonAncestor(root->left, p, q);
    //同时大于结点值
	if (root->val < p->val && root->val < q->val)
		return lowestCommonAncestor(root->right, p, q);
	//夹在中间
    return root;
    }
};

总结:

这道题根据搜素树的特性,比普通二叉树的二叉树更简单完成.