Authored by Tony Feng
Created on April 26th, 2022
Last Modified on April 26th, 2022
Task 1 - Q54. 二叉搜索树的第k大节点
Question
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
e.g. 输入: [5,3,6,2,4,null,null,1], k = 3; 输出: 4
1
2
3
4
5
6
7
|
5
/ \
3 6
/ \
2 4
/
1
|
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
nums = []
def dfs(node):
if len(nums) >= k or not node:
return
dfs(node.right)
nums.append(node.val)
dfs(node.left)
dfs(root)
return nums[k-1]
|
Explanation
- We can adopt the properties of binary tree by traversing the tree from the rightest node, which is a reversed version of inorder traverse.
- Time Complexity: O(N)
- Space Complexity: O(N)
Task 2 - Q36. 二叉搜索树与双向链表
Question
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。head 表示指向链表中有最小元素的节点。
Solution 1
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
|
class Solution: # Use a tmp list
def treeToDoublyList(self, root: TreeNode) -> TreeNode:
if not root:
return None
s = []
def dfs(node: TreeNode): # Inorder traverse
if node:
dfs(node.left)
s.append(node)
dfs(node.right)
# All nodes are stored in a list temporarily
dfs(root)
# Build doubly list
n = len(s)
for i in range(1, n - 1):
s[i].left = s[i - 1]
s[i].right = s[i + 1]
# Handle the first and last elements
head = s[0]
head.left = s[-1]
head.right = s[1] if n > 1 else head
if n > 1:
head.left.left = s[-2]
head.left.right = head
return head
|
Solution 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution: # DFS
def treeToDoublyList(self, root: TreeNode) -> TreeNode:
if not root:
return None
def dfs(cur: TreeNode): # Inorder traverse
if cur:
dfs(cur.left)
if self.pre:
self.pre.right, cur.left = cur, self.pre
else:
self.head = cur # head points to the leftest node
self.pre = cur
dfs(cur.right)
self.pre = None # global var
dfs(root)
self.head.left, self.pre.right = self.pre, self.head
return self.head
|
Explanation
- Solution 1 & 2:
- Time Complexity: O(N)
- Space Complexity: O(N)
Task 3 - Q34. 二叉树中和为某一值的路径
Question
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
Solution 1
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
|
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution: # DFS
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
if not root:
return []
res = []
def dfs(node, curSum, tmp):
curSum += node.val
tmp.append(node.val)
if not node.left and not node.right:
if curSum == target:
res.append(tmp[:])
return
if node.left:
dfs(node.left, curSum, tmp)
tmp.pop()
if node.right:
dfs(node.right, curSum, tmp)
tmp.pop()
dfs(root, 0, [])
return res
|
Solution 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution: # DFS
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res, path = [], []
def dfs(root, cnt):
if not root:
return
path.append(root.val)
cnt -= root.val
if cnt == 0 and not root.left and not root.right:
res.append(path[:])
dfs(root.left, cnt)
dfs(root.right, cnt)
path.pop()
dfs(root, sum)
return res
|
Explanation
- Solution 1 is my solution and Solution 2 is from others. Both of them adopt DFS, but they are slightly different.
- Time Complexity: O(N)
- Space Complexity: O(N)
