潍坊网站建设教程网络营销活动策划

题意，找到所有最深的叶子节点的LCA
https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/description/

第一个想法是模块的想法, LCA +找到所有最深的叶子节点两两组合 可行，但是算法复杂度很高而且你先要从顶到下，再从下到顶再算一遍算法复杂度太高

第二个想法，利用后续位置进行计算，好处是，我在后续位置可以知道更多的信息，比如左右子树的深度信息此时是已知的。二叉树的分治算法本质上是一种后序遍历。
构造一个函数，这个函数能够返回一个lcaDeepestLeaves+以root为根的树的深度，如果左子树的深度 > 右子树的深度，我只需要返回左子树的答案，因为这意味着左边深度大，右边的叶子节点都被舍弃了，反之对右子树也成立
但是如果一样深，那我要返回root

/*** 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) {return dfs(root).second;}pair<int, TreeNode*> dfs(TreeNode* node) {if (!node) {return {0, nullptr};}auto left = dfs(node->left);auto right = dfs(node->right);if(left.first > right.first) {return {left.first + 1, left.second};} elseif (left.first < right.first) {return {right.first + 1, right.second};}return {left.first + 1, node};}};