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 isd+1
. - The lowest common ancestor of a set
S
of nodes is the nodeA
with the largest depth such that every node in S is in the subtree with rootA
.
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
No comments:
Post a Comment