给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 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, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
解析:
dfs + 计数 即可
注意root为其中一个查找结点的情况
/** * 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: int dfs(TreeNode* &root, TreeNode* &p, TreeNode* &q, TreeNode* & father) { if(root == nullptr) return 0; int flag = 0; if(root == p || root == q) flag = 1; int flag1 = dfs(root->left, p, q, father); if(flag1 < 0) return -1; int flag2 = dfs(root->right, p, q, father); if(flag2 < 0) return -1; if(flag1 + flag2 + flag == 2) { father = root; return -1; } return flag1 + flag2 + flag; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(p == q) return p; TreeNode* father; dfs(root, p, q, father); return father; } };