-2
\$\begingroup\$

Introduction

124. Binary Tree Maximum Path Sum 's variant. But what difference is to output the non-repeating path list when the path sum is maximum.
It is an interview code problem I have met before in a Unicorn Company.

Challenge

In details, given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example Input and Output

The output is not strictly required in the interview process, but it should describe the whole path and is no-repeatin.
For example, it can be a traversal like follows.

Example 1:
Input: [1, 2, 3]

       1
      / \
     2   3

Output: [[2, 3, 1]]


Example 2:
Input: [-10, 9, 20, null, null, 15, 7]

   -10
   / \
  9  20
    /  \
   15   7

Output: [[15, 7, 15]]


Example 3:
Input: [-10, 9, 20, 15, 7, 15, 7]

    -10
   /    \
  20     20
 / \    /  \
15  7  15   7

Output: [[15, 7, 20]]


Example 4:
Input: [-10, 9, 20, 15, 7, 15, 7]

    -10
   /    \
  15     20
 / \    /  \
20  7  15   7

Output: [[20, 7, 15], [15, 7, 20]]


Example 5:
Input: [-10, 9, 20, 15, 7, 15, 7]

    -10
   /    \
  15     20
 / \    /  \
20  7  15   7
      /
     30

Output: [[30, 15, 7, 20]]

the code part is given here

/**
 * 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:
    vector<vector<int>> maxPathSum(TreeNode* root) {
        
    }
};

My Thoughts

If just one and no-repeating maximum sum path, I will try to record three nodes which are the root node of the subtree path, the bottom level left child of this subtree path, and the bottom level right child of this subtree path. And output the subtree path by a DFS traverse, like 20, 30, 7 in the Example 5
BUT if given a maximum sum repeating path, I don't know how to deal with it right.

| |
\$\endgroup\$
  • \$\begingroup\$ This is the meta code golf site, for asking questions about the site itself. But I think this question wouldn't be appropriate for the main site either, since it's asking for programming help. The site is about posing recreational challenges. \$\endgroup\$ – xnor Jun 29 at 12:40
  • 1
    \$\begingroup\$ Does this answer your question? Sandbox for Proposed Challenges \$\endgroup\$ – caird coinheringaahing Jun 29 at 13:51

Browse other questions tagged .