LCA of the Deepest Nodes

Given a tree, find the smallest subtree that contains all of the tree's deepest tree

Thoughts

分治, 递归统计每个子节点的深度, 当最深深度只出现一次时, 把那个子节点所对应的return直接返回(并深度加一), 当出现超过一次时, 说明任何子树都不包含包括所有deepest node的lca, 直接返回root.

Code

/**
 * 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 {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return helper(root, 0).first;
    }

private:
    pair<TreeNode*, int> helper(TreeNode* root, int depth) {
        if (!root) return {NULL, 0};
        const auto left = helper(root->left, depth + 1);
        const auto right = helper(root->right, depth + 1);
        if (left.second > right.second) {
            return left;
        } else if (right.second > left.second) {
            return right;
        } else {
            return {root, max(left.second, depth)};
        }
    }
};

  public class Result {
    TreeNode node;
    int depth;
    Result(TreeNode node, int depth) {
      this.node = node;
      this.depth = depth;
    }
  }

  public TreeNode lca(TreeNode node) {
    return helper(node).node;
  }

  public Result helper(TreeNode node) {
    if (node == null) {
      return new Result(null, 0);
    }
    int max = 0, count = 0;
    TreeNode target = node;
    for (TreeNode sub : node.children) {
      Result subres = helper(sub);
      if (subres.depth > max) {
        max = subres.depth;
        count = 1;
        target = subres.node;
      } else if (subres.depth == max) {
        count++;
        target = root;
      }
    }

    return new Result(target, max + 1);
  }