番禺品牌型网站,大连城乡建设局官网,wordpress 用ip访问,湖北网站设计给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大#xff08;一个节点也可以是它自己的祖… 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 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 。 因为根据定义最近公共祖先节点可以为节点本身。示例 3 输入root [1,2], p 1, q 2
输出1class Solution {
public:
bool find(TreeNode* root,TreeNode*x,stackTreeNode*path)
{ if(rootnullptr) return false;path.push(root);if(rootx) return true;if(find(root-left,x,path)) return true;if(find(root-right,x,path)) return true;path.pop();//左右都为空没找到肯定不是这条路了那就pop掉return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode*ppath,qpath;find(root,p,ppath);find(root,q,qpath);//找出p q的路径while(ppath.size()!qpath.size())//先让两条路径相同大小{ if(ppath.size()qpath.size()) ppath.pop();else qpath.pop();}
while(ppath.top()!qpath.top())//开始找祖先
{ppath.pop();qpath.pop();
}return ppath.top();}};
