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

╰+攻爆jí腚メ 2021-12-09 20:47 214阅读 0赞

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;
        }
    };