LeetCode 236 最近公共祖先 Lowest Common Ancestor of a Binary Tree
题目:找p和q的最近公共祖先
given a binary tree, find the lowest common ancestor (lca) of two given nodes in the tree.
according to the definition of lca on wikipedia: “the lowest common ancestor is defined between two nodes v and w as the lowest node in t that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4for example, the lowest common ancestor (lca) of nodes 5 and 1 is 3. another example is lca of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the lca definition.
理解：
当遍历到一个root点的时候，
1.判断root是不是null如果root为null，那么就无所谓祖先节点，直接返回null就好了
2.如果root的左子树存在p，右子树存在q，那么root肯定就是最近祖先
3.如果pq都在root的左子树，那么就需要递归root的左子树，右子树同理
treenode* lowestcommonancestor(treenode* root, treenode* p, treenode* q) { if(root == null || root == p || root ==q) return root; treenode* left = lowestcommonancestor(root->left, p, q); treenode* right = lowestcommonancestor(root->right, p, q); if(left && right){ return root; }else{ return left == null ? right : left; }}
在环幕轨道影院感受全新的视觉体验
2009年山寨本市场回顾和2010年的预测
华为荣耀Magic、小米MIX最难抢的国产手机，高颜值逼疯手机膜厂商
亿级像素,联想常程暗示Z6 Pro成首款摄像头像素逆天
IGBT和SiC栅极驱动器基础知识（一）
LeetCode 236 最近公共祖先 Lowest Common Ancestor of a Binary Tree
机器人没有生命的灵动和温情 并不会代替导盲犬
吉利发力15TD发动机 建5大工厂
浅谈三相异步电动机维修及保护研究
基于Altium designer的层次化的原理图设计
亿纬锂能违规暴雷！
苹果手机的几大缺点
如何鉴定户外LED广告屏的质量好坏
小马智行荣膺首个跨省自动驾驶重卡示范应用许可企业
血氧仪的曲线怎么看 血氧仪下面的波浪线是什么
高级程序员是怎样的
薄膜压电材料压电系数测试方法
Qualcomm助力打造600MHz Band 71移动终端
Agilex FPGA，现代FPGA技术的核心力量
中国电信5G SA网络创新对LTE核心网部署具有重要意义
given a binary tree, find the lowest common ancestor (lca) of two given nodes in the tree.
according to the definition of lca on wikipedia: “the lowest common ancestor is defined between two nodes v and w as the lowest node in t that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4for example, the lowest common ancestor (lca) of nodes 5 and 1 is 3. another example is lca of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the lca definition.
理解：
当遍历到一个root点的时候，
1.判断root是不是null如果root为null，那么就无所谓祖先节点，直接返回null就好了
2.如果root的左子树存在p，右子树存在q，那么root肯定就是最近祖先
3.如果pq都在root的左子树，那么就需要递归root的左子树，右子树同理
treenode* lowestcommonancestor(treenode* root, treenode* p, treenode* q) { if(root == null || root == p || root ==q) return root; treenode* left = lowestcommonancestor(root->left, p, q); treenode* right = lowestcommonancestor(root->right, p, q); if(left && right){ return root; }else{ return left == null ? right : left; }}
在环幕轨道影院感受全新的视觉体验
2009年山寨本市场回顾和2010年的预测
华为荣耀Magic、小米MIX最难抢的国产手机，高颜值逼疯手机膜厂商
亿级像素,联想常程暗示Z6 Pro成首款摄像头像素逆天
IGBT和SiC栅极驱动器基础知识（一）
LeetCode 236 最近公共祖先 Lowest Common Ancestor of a Binary Tree
机器人没有生命的灵动和温情 并不会代替导盲犬
吉利发力15TD发动机 建5大工厂
浅谈三相异步电动机维修及保护研究
基于Altium designer的层次化的原理图设计
亿纬锂能违规暴雷！
苹果手机的几大缺点
如何鉴定户外LED广告屏的质量好坏
小马智行荣膺首个跨省自动驾驶重卡示范应用许可企业
血氧仪的曲线怎么看 血氧仪下面的波浪线是什么
高级程序员是怎样的
薄膜压电材料压电系数测试方法
Qualcomm助力打造600MHz Band 71移动终端
Agilex FPGA，现代FPGA技术的核心力量
中国电信5G SA网络创新对LTE核心网部署具有重要意义