【Leetcode】1123. Lowest Common Ancestor of Deepest Leaves（二叉树最深叶子结点的公共父节点）

Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

• The node of a binary tree is a leaf if and only if it has no children
• The depth of the root of the tree is 0, and if the depth of a node is d, the depth of each of its children is d+1.
• The lowest common ancestor of a set S of nodes is the node A with the largest depth such that every node in S is in the subtree with root A.

Example 1:

Input: root = [1,2,3]
Output: [1,2,3]
Explanation: 
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".
  

Example 2:

Input: root = [1,2,3,4]
Output: [4]
  

Example 3:

Input: root = [1,2,3,4,5]
Output: [2,4,5]
  

Constraints:

• The given tree will have between 1 and 1000 nodes.
• Each node of the tree will have a distinct value between 1 and 1000.

题目大意：

找出最深的叶子结点（为空）的公共父节点。

解题思路：

找出当前节点的左右最大深度， 如果当前左右的最大深度相同，则说明当前节点是最大深度下叶子结点的父节点。

按照递归遍历的顺序来看，应该先遍历左右，最后判断父节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode *ans;
    int max_deep;
    
    int helper(TreeNode *root, int nums){
        
        if(root->left == NULL && root->right == NULL){
            if(nums>max_deep){
                ans = root;
                max_deep = nums;
            }
            return nums;
        }
        int num_l=0, num_r=0;
        if(root->left) num_l = helper(root->left, nums+1);
        if(root->right) num_r = helper(root->right, nums+1);
        
        if(num_l == num_r && num_l>=max_deep){
            ans = root;
            max_deep = num_l;
        }
        return max(num_l, num_r);
    }
    
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        ans = root;
        max_deep = INT_MIN;
        int deep_n = helper(root, 1);
        return ans;
    }
};