代理做减肥网站,flash网站模板 asp,网站关键词优化的步骤和过程,深圳网站开发哪个好题意#xff0c;找到所有最深的叶子节点的LCA https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/description/
第一个想法是模块的想法, LCA 找到所有最深的叶子节点两两组合 可行#xff0c;但是算法复杂度很高而且你先要从顶到下#xff0c;再从…题意找到所有最深的叶子节点的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;}pairint, 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};}};
