首页 > 试题广场 >

树上最长单色路径

[编程题]树上最长单色路径

热度指数：1893 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一棵由黑白点组成的二叉树，我们需要找到其中最长的单色简单路径，其中简单路径的定义是从树上的某点开始沿树边走不重复的点到树上的另一点结束而形成的路径，而路径的长度就是经过的点的数量(包括起点和终点)。而这里我们所说的单色路径自然就是只经过一种颜色的点的路径。你需要找到这棵树上最长的单色路径。

给定一棵二叉树的根节点(树的点数小于等于300，请做到O(n)的复杂度)，请返回最长单色路径的长度。这里的节点颜色由点上的权值表示，权值为1的是黑点，为0的是白点。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

JchengGit

超级简洁的Python实现

在递归中每次返回当前节点的最大高度，在递归之外记录一个出现过的最大长度。

class LongestPath:
    
    def __init__(self):
        self.maxlong = 0 #用来记录递归过程中出现过的最大长度
        
    def findPath(self, root):
        self.findeach(root)
        return self.maxlong #返回最终结果
        
    def findeach(self, root):
        if root.left is not None:
            x = self.findeach(root.left) #只要左子树不为空就递归一次
            ml = x if root.left.val == root.val else 0
        else:
            ml = 0 #ml是左子树的最大高度，颜色不同则为0
            
        if root.right is not None:
            y = self.findeach(root.right)
            mr = y if root.right.val == root.val else 0
        else:
            mr = 0
        
        maxhigh = max(ml,mr)+1 #当前节点的最大高度
        maxlong = ml+mr+1 #左子树高度+右子树高度+1=当前节点最大路径长度
        
        if maxlong>self.maxlong:
            self.maxlong = maxlong #更新最大长度
        return maxhigh

编辑于 2020-02-21 22:13:27 回复(0)

Python

Coast2

# -*- coding:utf-8 -*-
#coding=utf-8
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class LongestPath:
    def getPath(self,root): ###返回以root为根节点的树中的最长路径（最长相同颜色的节点路径）和最长单向路径（以root为末节点的一条路径）
        if(root==None):
            return 0,0;
        cur_MaxLen=1;
        cur_MaxOneSide=1;
        left_maxLen,right_maxLen=0,0;
        if(root.left):
            left_maxLen,left_maxOneSide=self.getPath(root.left);
            if(root.left.val==root.val):
                cur_MaxLen+=left_maxOneSide;
                cur_MaxOneSide=max(cur_MaxOneSide,left_maxOneSide+1);
        if(root.right):
            right_maxLen,right_maxOneSide=self.getPath(root.right);
            if(root.right.val==root.val):
                cur_MaxLen+=right_maxOneSide;
                cur_MaxOneSide=max(cur_MaxOneSide,right_maxOneSide+1);      
        return max([cur_MaxLen,left_maxLen,right_maxLen]),cur_MaxOneSide;
    def findPath(self,root):
        return  self.getPath(root)[0];

编辑于 2016-09-09 00:02:54 回复(0)