每天一道编程题——树上最长单色路径

Code

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Node:
    def __init__(self, value=None, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right
# TREE = Node(0,
#             Node(1, Node(1), Node(0)),
#             Node(0, Node(0), Node(1))
#             )
TREE = Node(0,
            Node(1, Node(0, Node(1, Node(1))), Node(0)),
            Node(1, Node(0), Node(0))
            )
def func(root):
    B_res, W_res = [], []
    def res(root, W, B):
        if root == None:
            B_res.append(B)
            W_res.append(W)
            return
        if root.val == 0:
            W += 1
            B_res.append(B)
            B = 0
        elif root.val == 1:
            B += 1
            W_res.append(W)
            W = 0
        res(root.left, W, B)
        res(root.right, W, B)
    res(root, 0, 0)
    return max(max(B_res), max(W_res))

来自“一战通offer”互联网实习季编程挑战

本文标题:每天一道编程题——树上最长单色路径

文章作者:Vincent Zhong

发布时间:2016-10-08, 23:22:48

最后更新:2019-07-07, 13:13:10

原始链接:https://wax8280.github.io/2016/10/08/每天一道编程题——树上最长单色路径/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
|