LC Python 刷题笔记有志者事竟成

李浩泉

LC上标的是中等难度，但是也是简单的基础概念，需要二叉树遍历

# 199 Binary Tree Right Side View

'''
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
'''
def rightSideView(self, root: TreeNode) -> List[int]:
if not root : return []
result = []
current = []
current.append(root)
while current :
next_level = []
value = []
for n in current :
value.append(n.val)
if n.right :
next_level.append(n.right)
if n.left :
next_level.append(n.left)
current = next_level
result.append(value)
s = []
for i in range(len(result)):
s.append(result[i][0])
return s

复制代码

李浩泉

# 671 Second Minimum Node In a Binary Tree

一样的方法，先遍历出所有的值，然后从中找出第二小的值。不一定是最优解，但是是最容易理解和在面试时快速做出来不出错的方法之一。

'''
Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.
Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.
If no such second minimum value exists, output -1 instead.
Example 1:
Input:
2
/ \
2 5
/ \
5 7
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:
Input:
2
/ \
2 2
Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
'''
def findSecondMinimumValue(self, root: TreeNode) -> int:
if not root: return -1
result = []
current = []
current.append(root)
while current:
next_level = []
for n in current:
result.append(n.val)
if n.left:
next_level.append(n.left)
if n.right:
next_level.append(n.right)
current = next_level
s = set(result)
l = list(s)
l.sort()
if len(l) > 1 : return l[1]
else: return -1

复制代码

wuwendongxi

你把进大厂看的太简单了。刷题只是过code那一轮，还有系统设计。两手都要抓，两手都要硬。

李浩泉

二叉树基础操作 - 遍历

1. Not Layer by Layer

if not root: return []
result = []
current = []
current.append(root)
while current:
next_level = []
for n in current:
result.append(n.val)
if n.left:
next_level.append(n.left)
if n.right:
next_level.append(n.right)
current = next_level
return result

复制代码

2. Layer by Layer

if not root: return []
result = []
current = []
current.append(root)
while current:
next_level = []
value = []
for n in current:
value.append(n.val)
if n.left:
next_level.append(n.left)
if n.right:
next_level.append(n.right)
current = next_level
result.append(value)
return result

复制代码

niuhj

可以啊，不过平推真的不适合啊，最好是按topic先刷，再随机平推检验

李浩泉

本帖最后由李浩泉于 2020-8-1 09:11 编辑

二叉树基础题里面另外一类就是：构建子函数，用 Recursion 递归

# 543 Diameter of Binary Tree

Complexity Analysis

Time Complexity: I visit every node once, so it is O(N).

Space Complexity: O(N).

'''
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
'''
def diameterOfBinaryTree(self, root):
def longpath(y):
if not y : return 0
r = longpath(y.right)
l = longpath(y.left)
self.result = max(self.result, r + l + 1 )
return max(l,r) + 1
self.result = 1
longpath(root)
return self.result - 1

复制代码

李浩泉

二叉树里面用递归的还有一种就是，不设子函数，就是用self，自己call自己，我也是看了答案之后，才敢用的。

# 235 Lowest Common Ancestor of a Binary Search Tree

'''
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
'''
def lowestCommonAncestor(self,root,p,q):
if not root: return root
if root.val == p.val or root.val == q.val:
return root
l = self.lowestCommonAncestor(root.left, p, q)
r = self.lowestCommonAncestor(root.right, p, q)
if l and r:
return root
return l or r

复制代码

李浩泉

# 236 Lowest Common Ancestor of a Binary Tree

和235一样，用self去做

'''
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
'''
def lowestCommonAncestor(self, root, p, q):
if not root: return root
if root.val == p.val or root.val == q.val:
return root
l = self.lowestCommonAncestor(root.left, p, q)
r = self.lowestCommonAncestor(root.right, p, q)
if l and r:
return root
return l or r

复制代码

如果不用self去做，下面这个方法就比较难了

def lowestCommonAncestor(self, root, p, q):
stack = [root]
parent = {root: None}
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return q

复制代码

李浩泉

# 257 Binary Tree Paths

这道题太经典了，构建子函数递归Recursion，然后在子函数内部继续call子函数自己。

'''
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input:
1
/ \
2 3
\
5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
'''
def binaryTreePaths(self, root: TreeNode) -> List[str]:
def construct_paths(root, path):
if root:
path += str(root.val)
if not root.left and not root.right: # if reach a leaf
paths.append(path) # update paths
else:
path += '->' # extend the current path
construct_paths(root.left, path)
construct_paths(root.right, path)
paths = []
construct_paths(root, '')
return paths

复制代码

李浩泉

# 700 Search in a Binary Search Tree

同样的方法，call self.****，然后递归。

'''
Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.
For example,
Given the tree:
4
/ \
2 7
/ \
1 3
And the value to search: 2
You should return this subtree:
2
/ \
1 3
In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.
Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.
'''
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if root is None or val == root.val:
return root
if val < root.val:
return self.searchBST(root.left, val)
else:
return self.searchBST(root.right, val)

复制代码

[Leetcode] LC Python 刷题笔记有志者事竟成

浏览过的版块

[Leetcode] LC Python 刷题笔记 有志者事竟成

浏览过的版块

[Leetcode] LC Python 刷题笔记有志者事竟成