undefined

二叉树专题–输出根节点到所有叶子节点的路径：https://blog.csdn.net/SHENMEGUI_32/article/details/77661785

求二叉树的一条最长路径并且打印，如果有多条，输出其中一条。利用二叉树的套路来做。树形 DP 问题，想要从子树要什么信息？

// 求二叉树的最长直径并且打印
struct ReturnValuePath {
    int length;
    std::vector<int> nodes;
public:
    explicit ReturnValuePath(int length, std::vector<int> nodes) : length(length), nodes(std::move(nodes)) {}
};

// 可以得到当前输入的节点，左右子树中最长的路径和长度
ReturnValuePath* getMaxPathSub(TreeNode* root) {
    if (root == nullptr) {
        return new ReturnValuePath(0, std::vector<int>());
    }
    if (root->left == nullptr && root->right == nullptr) {
        return new ReturnValuePath(1, std::vector<int>{root->val});
    }
    auto left_ret = getMaxPathSub(root->left);
    auto right_ret = getMaxPathSub(root->right);
    int length = 0;
    std::vector<int> nodes;
    // 此时对于 root 节点来说，要判断 root 的左树和右树之间，那个树的长度更长
    if (left_ret->length > right_ret->length) {
        length = left_ret->length + 1;
        nodes.insert(nodes.end(), left_ret->nodes.begin(), left_ret->nodes.end());

    } else {
        length = right_ret->length + 1;
        nodes.insert(nodes.end(), right_ret->nodes.begin(), right_ret->nodes.end());
    }
    nodes.push_back(root->val);
    return new ReturnValuePath(length, nodes);
}

int max_length_path = INT_MIN;
std::vector<int> max_nodes_path;

// 然后可以遍历所有节点，然后进行比较对比
void getMaxPath(TreeNode* root) {
    if (root == nullptr) return;
    auto left_ret = getMaxPathSub(root->left);
    auto right_ret = getMaxPathSub(root->right);
    if (left_ret->length + right_ret->length + 1 > max_length_path) {
        max_length_path = left_ret->length + right_ret->length + 1;
        std::vector<int> cur_nodes(left_ret->nodes.begin(), left_ret->nodes.end());
        cur_nodes.push_back(root->val);
        cur_nodes.insert(cur_nodes.end(), right_ret->nodes.rbegin(), right_ret->nodes.rend());
        max_nodes_path.swap(cur_nodes);
    }
    getMaxPath(root->left);
    getMaxPath(root->right);
}