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

2021年09月15日 阅读数:2
这篇文章主要向大家介绍[LintCode] 619 Binary Tree Longest Consecutive Sequence III 二叉树最长连续序列 III,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

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
java

解法:和Binary Tree Longest Consecutive Sequence II同样的作法。II只要check一下left和right。这题由于有多个子节点,因此要用一个循环来check全部。

Java:node

 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);
    }

  

相似题目:post

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

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