求二叉樹中最長的之字形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