forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdiameter-of-binary-tree.py
More file actions
85 lines (67 loc) · 2.98 KB
/
diameter-of-binary-tree.py
File metadata and controls
85 lines (67 loc) · 2.98 KB
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#https://leetcode.com/problems/diameter-of-binary-tree/
#what we want to find?
#max depth that goes right add max depth that goes left
#it could be from any node
#so we iterate through every node to update our the diameter to max
class Solution(object):
def diameterOfBinaryTree(self, root):
self.diameter = 0
def traverse(node):
if not node: return 0
#the max depth go left from this node
#the max depth go right from this node
left, right = traverse(node.left), traverse(node.right)
#update diameter if left+right is bigger
self.diameter = max(self.diameter, left+right)
#add 1 is for the step that get to this node
#max(left, right) is for the left or right path that goes to the deepest
return max(left, right)+1
#iterate through the tree
traverse(root)
return self.diameter
#2020
class Solution(object):
def diameterOfBinaryTree(self, root):
def getMaxDepth(node):
if not node: return 0
l, r = getMaxDepth(node.left), getMaxDepth(node.right)
self.ans = max(self.ans, l+r)
return max(l, r)+1 #add the node it self
if not root: return 0
self.ans = float('-inf')
getMaxDepth(root)
return self.ans
"""
What we want to find?
From an unknown node, that its max_depth_from_left (`l`) + max_depth_from_right (`r`) is the biggest.
The node that generate this number could be from any node, so we iterate through every node to update `ans`.
In other words, to find the answer, we need to check every node, if the max diameter pass through here.
Time complexity is O(N), where N is the number of nodes.
Space complexity is O(LogN), since we might got to LogN level on recursion.
"""
# from collections import defaultdict
# class Solution(object):
# def diameterOfBinaryTree(self, root):
# def getLeftLength(node):
# if not node: return -1
# if not (node in record and 'left' in record[node]):
# record[node]['left'] = max(getLeftLength(node.left), getRightLength(node.left))+1
# return record[node]['left']
# def getRightLength(node):
# if not node: return -1
# if not (node in record and 'right' in record[node]):
# record[node]['right'] = max(getLeftLength(node.right), getRightLength(node.right))+1
# return record[node]['right']
# if not root: return 0
# record = defaultdict(dict)
# ans = float('-inf')
# stack = []
# stack.append(root)
# while stack:
# node = stack.pop()
# if not node: continue
# d = getLeftLength(node)+getRightLength(node)
# ans = max(ans, d)
# stack.append(node.left)
# stack.append(node.right)
# return ans