公司网站做优化,注册域名之后如何建设网站,php+mysql 2012也买酒商城网站源码,电商网站页面分类给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为#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
输出1提示 树中节点数目在范围 [2, 105] 内。-109 Node.val 109所有 Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。 跟着左神的视频课参考了左神的解题方法不过时间上打败30%记录一下以后提升。
TreeNode* find(TreeNode* cur){if(cur NULL) return NULL;if(cur Gp || cur Gq) return cur;TreeNode* left find(cur-left);TreeNode* right find(cur-right);if(left ! NULL right ! NULL){return cur;}return left NULL ? right : left;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {Groot root;Gp p;Gq q;return find(root);} 一样的代码又提交了一遍时间反而变少了真的神奇
