Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求二叉树中最长的之字形path,DFS


 1 #1372
 2 #Runtime: 366 ms (Beats 100%)
 3 #Memory: 64.2 MB (Beats 66.67%)
 4 
 5 # Definition for a binary tree node.
 6 # class TreeNode(object):
 7 #     def __init__(self, val=0, left=None, right=None):
 8 #         self.val = val
 9 #         self.left = left
10 #         self.right = right
11 class Solution(object):
12     def longestZigZag(self, root):
13         """
14         :type root: TreeNode
15         :rtype: int
16         """
17         self.ans = 0
18 
19         def DFS(node, pre, length):
20             if not node:
21                 return
22             if length > self.ans:
23                 self.ans = length
24             if pre == -1:
25                 DFS(node.left, 0, length + 1)
26                 DFS(node.right, 1, length + 1)
27             elif pre == 0:
28                 DFS(node.left, 0, 1)
29                 DFS(node.right, 1, length + 1)
30             else:
31                 DFS(node.left, 0, length + 1)
32                 DFS(node.right, 1, 1)
33 
34         DFS(root, -1, 0)
35         return self.ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理