站长工具seo推广,云南网站设计平台,网站开发销售怎么做,河源新闻最新消息文章目录 题目思路代码结果 题目
题目链接 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个结点 p、q#xff0c;最近公共祖先表示为一个结点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度… 文章目录 题目思路代码结果 题目
题目链接 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。 思路
我们可以使用遍历的方式寻找通往 p 和 q 节点路径。我们可以考虑将这两个节点放在一起遍历从而避免存储路径所需的空间。 遍历过程如下
从根节点开始遍历。如果当前节点的值大于 p 和 q 的值则 p 和 q 应该在当前节点的左子树将当前节点移动到其左子节点。如果当前节点的值小于 p 和 q 的值则 p 和 q 应该在当前节点的右子树将当前节点移动到其右子节点。如果当前节点的值不满足上述两条要求则当前节点是分岔点。此时p 和 q 要么在当前节点的不同子树中要么其中一个就是当前节点。
这种方法省去了存储路径所需的空间提高了效率。
代码
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root NULL) return NULL;if (root-val p-val || root-val q-val) return root;TreeNode* left lowestCommonAncestor(root-left, p, q), * right lowestCommonAncestor(root-right, p, q);if (left NULL) return right;if (right NULL) return left;return root;}
};结果
