『递归的妙用』题解 | #在二叉树中找到两个节点的最近公共祖先#
在二叉树中找到两个节点的最近公共祖先
http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
需要多做几遍的题目。。
- 『刚开始做的时候卡了。。。』
- 递归的妙用
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
if( nullptr==root ) return 0x3f3f3f;//表示没有公共祖先
if( o1==root->val || o2==root->val )
{
return root->val;//当前节点就是最近公共祖先
}
//去左子树找最近公共祖先
int Left=lowestCommonAncestor( root->left , o1, o2);
//去右边子树找最近公共祖先
int Right=lowestCommonAncestor( root->right , o1, o2);
if( 0x3f3f3f==Right ) return Left;
if( 0x3f3f3f==Left ) return Right;
return root->val;
}
}; 
查看8道真题和解析
投递美团等公司10个岗位 >