Leetcode 1123. 最深叶节点的最近公共祖先（DAY 9）

原题题目

代码实现（首刷自解需要计算深度）

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int maxlevel;
struct TreeNode* ans;bool visit(struct TreeNode* root,int level)
{
    if(!root)return false;bool left = visit(root->left,level+1);bool right = visit(root->right,level+1);if(left && right || level + 1 == maxlevel){
    ans = root;return true;}return left || right;
}void maxheight(struct TreeNode* root,int level)
{
    if(root){
    maxheight(root->left,level+1);maxheight(root->right,level+1);if(level + 1 > maxlevel)maxlevel = level + 1;}
}struct TreeNode* lcaDeepestLeaves(struct TreeNode* root){
    maxlevel = 0;ans = NULL;maxheight(root,0);visit(root,0);return ans;
}

代码实现（递归）

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
struct TreeNode* ans;int dfs(struct TreeNode* root)
{
    if(!root)return 0;return fmax(dfs(root->left),dfs(root->right)) +1;
}
struct TreeNode* lcaDeepestLeaves(struct TreeNode* root){
    int left = dfs(root->left);int right = dfs(root->right);if(left == right)return root;return left > right ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right);
}