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

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

有人可以帮助 proceed.Thanks..

编辑：我在采访中被问到这个问题作为树直径问题的后续问题。

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

变量'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' 这样的变量并在每个节点跟踪 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

可能会有一些 off by 1 的错误，如果有请指出，但应该可以。复杂度为 O(n).

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

Longest path in a binary tree with at most one turn

algorithm

tree

binary-tree