Tree #54
Comments
跟高度密切结合的题目104. Maximum Depth of Binary TreeTime: O(N) Proportional to input nodes, Iterates all nodes once. Base Case: 当Node为空的时候，返回高度为0 Recursive Rule精确版本 : Recursive Rule说人话: class Solution(object):
def maxDepth(self, root):
if not root: return 0
left = self.maxDepth(root.left)
right= self.maxDepth(root.right)
return max(left, right) + 1559. Maximum Depth of N-ary TreeBase Case: Recursive Rule精确版本 : Recursive Rule说人话: 换汤不换药做法Time: O(N) Proportional to input nodes, Iterates all nodes once. # Readable
class Solution(object):
def maxDepth(self, root):
if not root: return 0
if not root.children: return 1
height = []
for node in root.children:
height.append(self.maxDepth(node))
return max(height) + 1
#Pythonic
class Solution(object):
def maxDepth(self, root):
if not root: return 0
if not root.children: return 1
height = [self.maxDepth(node) for node in root.children]
return max(height) + 1利用变量代替每层的Temporary ListTime: O(N) Proportional to input nodes, Iterates all nodes once. class Solution(object):
def maxDepth(self, root):
if not root: return 0
height = 0
for node in root.children:
height = max(self.maxDepth(node), height)
return height + 1543. Diameter of Binary TreeBase Case: Recursive Rule : 题解思路 这题的Recursive Rule基本等同于LC104，唯一区别是在向上反的过程中，计算了当前层的Node的边长: 也就是左右孩子传递上来的高度之和，因为这道题的定义是求取最长的边长，所以当前层数的边长还需要和全球变量比对，然后更新全球变量的值
代码 Time: O(N) Proportional to input nodes, Iterates all nodes once. class Solution(object):
def diameterOfBinaryTree(self, root):
self.max_diameter = 0
self.dfsHelper(root)
return self.max_diameter
def dfsHelper(self, root):
if not root: return 0
left = self.dfsHelper(root.left)
right = self.dfsHelper(root.right)
cur_diameter = left + right
self.max_diameter = max(self.max_diameter, cur_diameter)
return max(left, right) + 1 |
两个Node之间的比较，跟换一类题100. Same TreeTime: O(N + M) Proportional to input nodes, Iterates all nodes once. Base Case: 当任意Node触底，比较该Node和另一个传递下来的Node的关系 Recursive Rule: class Solution(object):
def isSameTree(self, p, q):
# Base: 平衡的情况
if not p and not q: return True
if not p or not q: return False
# 索取: 两个Node的左孩子和右孩子是否相等
left = self.isSameTree(p.left, q.left)
right = self.isSameTree(p.right, q.right)
# 如果Value一样，返回True。
return p.val == q.val and left and right101. Symmetric TreeTime: O(N) Proportional to input nodes, Iterates all nodes once. Base Case: 当任意Node触底，比较该Node和另一个传递下来的Node的关系 Recursive Rule: class Solution(object):
def isSymmetric(self, root):
if not root: return True
return self.isSymmetricHelper(root.left, root.right)
def isSymmetricHelper(self, n1, n2):
# Base Case：当两个Node任意触底，是否平衡
if not n1 and not n2: return True
if not n1 or not n2: return False
# 传递： 2个Node
# 索取: 子孩子是否Symmetric
out_nodes = self.isSymmetricHelper(n1.left, n2.right)
in_nodes = self.isSymmetricHelper(n1.right, n2.left)
# 返回: 解决了两个Base case后，如果两个数相等，返回True
return n1.val == n2.val and out_nodes and in_nodes965. Univalued Binary TreeTime: O(N) Proportional to input nodes, Iterates all nodes once. Base Case: 当Node为空的时候，返回True Recursive Rule : class Solution(object):
def isUnivalTree(self, root):
if not root: return True
return self.dfsHelper(root.val, root)
def dfsHelper(self, target, root):
if not root: return True
left = self.dfsHelper(target, root.left)
right = self.dfsHelper(target, root.right)
return root.val == target and left and right226. Invert Binary TreeTime: O(N) Proportional to input nodes, Iterates all nodes once. Base Case: 当任意Node触底，比较该Node和另一个传递下来的Node的关系 Recursive Rule: class Solution(object):
def invertTree(self, root):
if not root: return
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right ; root.right = left
return root |
|
楼主加油！之前想跟着您刷题的，后面工作太忙跟不上了。您这样努力刷题，一定会有好结果的！不要放弃！ |
|
加油，之前断断续续刷过，最近看到楼主在leetcode上的题解，追到了github，受益匪浅。还在想楼主是否已经拿到offer了，因为已经有一段时间没有更新了。公瑾加油，肯定没问题的。 |
造树的一类题 |
BFS + 层级遍历102. Binary Tree Level Order Traversalfrom collections import deque
class Solution:
def levelOrder(self, root):
if not root: return []
queue, res = deque([root]), []
while queue:
cur_level, size = [], len(queue)
for i in range(size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
cur_level.append(node.val)
res.append(cur_level)
return res993. Cousins in Binary Treefrom collections import deque
class Solution(object):
def isCousins(self, root, x, y):
queue = deque([root])
while queue:
size, temp = len(queue), {}
for i in range(size):
node = queue.popleft()
if node.left:
queue.append(node.left)
temp[node.left.val] = node.val
if node.right:
queue.append(node.right)
temp[node.right.val] = node.val
if x in temp and y in temp:
return temp[x] == temp[y]
return False |
|
楼主加油！今年秋天就要作为new graduate开始找全职了，希望能通过参考您刷题的足迹拿到理想的offer |
妈蛋。FLAG全挂，今年9月再来一次，好好刷题。
The text was updated successfully, but these errors were encountered: