二叉树中最长的路径,最多一圈

Question

我在接受采访时遇到过这个问题.

给定二叉树,找到最多一个转弯的最长路径长度.路径的一端必须是一片叶子.另一端可以是叶子或任何节点.

转弯定义为:

In tree1-> start from 1 and there is a turn at root 2 towards right,
In tree2-> starts from 3 goes in left and there is a turn at 1 towards right ,
In tree3-> starts from 1 goes in right and there is a turn at 3 towards left,

     2                 3                 1
    / \               /                   \
   1   3             1                     3
                      \                    /
                       2                  2

一些人可以帮助如何继续.谢谢..

编辑:在采访中,我被问到这个问题是树问题直径的后续问题.

我对树的直径的实现是这样的.

变量'res'包含最终答案.

int maxPathSumUtil(struct Node *root, int &res)
{
    // Base case
    if (root==NULL) return 0;

    // Find maximum sum in left and right subtree. Also find
    // maximum root to leaf sums in left and right subtrees
    // and store them in lLPSum and rLPSum
    int lLPSum = maxPathSumUtil(root->left, res);
    int rLPSum = maxPathSumUtil(root->right, res);

    // Find the maximum path sum passing through root
    int curr_sum = max(lLPSum+rLPSum+root->data);

    // Update res (or result) if needed
    if (res < curr_sum)
        res = curr_sum;

    // Return the maximum root to leaf path sum
    return max(lLPSum, rLPSum)+root->data;
}

最初我认为我可以使用像'turns'这样的变量来提出解决方案,并在每个节点上跟踪转弯变量.

但我很少跟踪二叉树中的转弯.

Answer 1

我们可以使用动态编程.

让:

d[i] = longest path with at most one turn node such that i is the turn node
d_up[i, dir] = longest straight path from i to one of its ancestors
               coming from direction dir
d_down[i, dir] = similarly, except going to descendants.

我们有:

d[i] = max(d_up[i, R] + d_down[i, R],
           d_up[i, R] + d_down[i, L],
           d_up[i, L] + d_down[i, R],
           d_up[i, L] + d_down[i, L],
           d_down[i, L] + d_down[i, R])

这些都可以通过任何节点的单个DFS遍历来计算.伪代码:

DFS(i, direction):

  if i.left != null:
    d_up[i.left, L] = d_up[i, L] + 1
    d_down[i, L] = 1 + DFS(i.left, L)

  if i.right != null:
    d_up[i.right, R] = d_up[i, R] + 1
    d_down[i, R] = 1 + DFS(i.right, R)

  d[i] = max(d_up[i, R] + d_down[i, R],
             d_up[i, R] + d_down[i, L],
             d_up[i, L] + d_down[i, R],
             d_up[i, L] + d_down[i, L],
             d_down[i, L] + d_down[i, R])

  return 0

可能会有一些错误,如果是这样,请指出它们,但它应该有效.复杂性是O(n).