[LintCode] 619 Binary Tree Longest Consecutive Sequence III 二叉树最长连续序列 III

Given a k-ary tree, find the length of the longest consecutive sequence path.

The path could be start and end at any node in the tree

Example
An example of test data: k-ary tree 5<6<7<>,5<>,8<>>,4<3<>,5<>,3<>>>, denote the following structure:
5
/ \
6 4
/|\ /|\
7 5 8 3 5 3
Return 5, // 3-4-5-6-7

解法：和Binary Tree Longest Consecutive Sequence II一样的做法。II只要check一下left和right。这题因为有多个子节点，所以要用一个循环来check所有。

Java:

 class ResultType {

        int globalMax;

        int maxUp;

        int maxDown;

        public ResultType(int globalMax, int maxUp, int maxDown) {

            this.globalMax = globalMax;

            this.maxUp = maxUp;

            this.maxDown = maxDown;

        }

    }

    public int longestConsecutive3(MultiTreeNode root) {

        return helper(root).globalMax;

    }

    public ResultType helper(MultiTreeNode root) {

        if (root == null) {

            return new ResultType(0, 0, 0);

        }

        int maxUp = 0;

        int maxDown = 0;

        int max = Integer.MIN_VALUE;

        for (MultiTreeNode child : root.children) {

            if (child == null) {

                continue;

            }

            ResultType childResult = helper(child);

            if (child.val + 1 == root.val) {

                maxDown = Math.max(maxDown, childResult.maxDown + 1);

            }

            if (child.val - 1 == root.val) {

                maxUp = Math.max(maxUp, childResult.maxUp + 1);

            }

            max = Math.max(Math.max(max, childResult.globalMax), maxUp + maxDown + 1);

        }

        return new ResultType(max, maxUp, maxDown);

    }

类似题目：

[LeetCode] 298. Binary Tree Longest Consecutive Sequence 二叉树最长连续序列

[LeetCode] 549. Binary Tree Longest Consecutive Sequence II 二叉树最长连续序列之 II

巴特西

[LintCode] 619 Binary Tree Longest Consecutive Sequence III 二叉树最长连续序列 III

最新文章

热门文章