时间戳

首页 > 解决方案 > 我需要对我的算法进行评论，以在二叉树中找到最长的连续序列

java - 我需要对我的算法进行评论，以在二叉树中找到最长的连续序列

问题描述

// Save the sequence with the maximum length
private static int max = 1;

/**
 * The method goal is to find the longest numerical sequence in binary tree
 * 
 * @param t - the tree for the searching
 * @param next - save the current sequence, the sequence to compare with the max
 */
public static void longestSeqPath(BinNode t, int next) {
    if (t == null)
        return;

    /*
     * First we check if we have any left then we check if the left node value is consecutive to the current node
     * if it is, we start with the counting
     */
    if (t.hasLeft() && t.getLeft().getValue() == t.getValue() + 1 || t.hasRight() && t.getRight().getValue() == t.getValue() + 1) {
        next++;
    } else if (next > max) {
        max = next;
        next = 1;
    }
    longestSeqPath(t.getLeft(), next);
    longestSeqPath(t.getRight(),next);

    // Note: Next is equals to 1 because we don't start to count the sequence from the first number in the sequence
}

算法是否正确并解决了问题？算法有效吗？我能做得更有效吗？

我是新来的，正在学习如何提问。如果有什么需要解决的问题，我很乐意提出建议。

标签： javaalgorithmdata-structuresbinary-treereview

解决方案

想想如果你在数组中解决同样的问题：

for (i = 0; i < length; i++)
{
    // do all your logic here using a[i]
}

如果您正在对二叉树进行中序遍历，则变为：

void inorder(node)
{
    if (node == null) return;

    inorder(node.left);
    // do all your logic here, using node.value
    inorder(node.right);
}

推荐阅读