1123. Lowest Common Ancestor of Deepest Leaves -------M

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.

A:

就是每次记录左边和右边的最深，和已经找到的LCA node.

     /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* lcaDeepestLeaves(TreeNode* root) {
            int maxDepth=0;
            return helper(root, 0,maxDepth);
        }
    private:
        TreeNode* helper(TreeNode* root, int curDepth, int & maxDepth){
            if(not root)
                return nullptr;
            if(not root->left and not root->right){
                maxDepth = curDepth;
                return root;
            }
            int leftMost = 0;
            TreeNode* l = helper(root->left,curDepth+1, leftMost);

            int rightMost = 0;
            TreeNode* r = helper(root->right,curDepth+1, rightMost);

            if(leftMost > rightMost){
                maxDepth = leftMost;
                return l;
            }else if( leftMost < rightMost ){
                maxDepth = rightMost;
                return r;
            }else{ // equal depth
                maxDepth = rightMost;
                return root;
            }
        }
    };

哎， 很SB的错误， copy 的时候， 调用了2次 root->left, 没改成root->right.  TNND