- 思路
- example
- 迭代盘榨，層序遍歷bfs ，最后一層第一個節(jié)點蟆融。
- 復雜度. 時間：O(n), 空間: O(n)
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
que = collections.deque()
res = -1
if root:
que.append(root)
while que:
size = len(que)
for i in range(size):
node = que.popleft()
if i == 0:
if node.left == None and node.right == None:
res = node.val
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
return res
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
que = collections.deque()
res = -1
if root:
que.append(root)
while que:
size = len(que)
for i in range(size):
node = que.popleft()
if i == 0:
res = node.val
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
return res
- 遞歸草巡，前序（自上而下）, dfs， 回溯
- 左下角：
－ 葉子：node的children 為空
- 最下一層最左葉子： 利用depth 來判斷是否最下一層, 前序遍歷保證了第一個更新depth的節(jié)點為最左葉子型酥。
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
def traversal(root, depth):
nonlocal max_depth, res
if root.left == None and root.right == None:
if depth > max_depth:
max_depth = depth
res = root.val
return
if root.left:
depth += 1
traversal(root.left, depth)
depth -= 1
if root.right:
depth += 1
traversal(root.right, depth)
depth -= 1
max_depth= -float('inf')
res = -float('inf')
traversal(root, 1)
return res
- 思路
- example
- 給你二叉樹的根節(jié)點 root 和一個表示目標和的整數(shù) targetSum 山憨。判斷該樹中是否存在 根節(jié)點到葉子節(jié)點 的路徑查乒，這條路徑上所有節(jié)點值相加等于目標和 targetSum 。如果存在郁竟，返回 true 玛迄；否則，返回 false 棚亩。
- 遞歸蓖议，前序，回溯
- 遞歸函數(shù)傳遞參數(shù)pathsum讥蟆，返回值 True or False勒虾，方便提早退出遍歷。
- 也可以維護當前path與targetsumr的差值瘸彤。
- 復雜度. 時間：O(n), 空間: O(n)
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def traversal(root, pathsum):
if root.left == None and root.right == None:
if pathsum == targetSum:
return True
else:
return False
if root.left:
pathsum += root.left.val
flag = traversal(root.left, pathsum)
if flag:
return True
pathsum -= root.left.val
if root.right:
pathsum += root.right.val
flag = traversal(root.right, pathsum)
if flag:
return True
pathsum -= root.right.val
return False
if root == None:
return False
return traversal(root, root.val)
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def traversal(root, pathSum):
if root.left == None and root.right == None:
if pathSum == targetSum:
return True
else:
return False
if root.left:
flag = traversal(root.left, pathSum + root.left.val)
if flag:
return True
if root.right:
flag = traversal(root.right, pathSum + root.right.val)
if flag:
return True
return False
if root == None:
return False
return traversal(root, root.val)
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def traverse(root):
nonlocal pathSum
if root.left == None and root.right == None:
if pathSum == targetSum:
return True
else:
return False
if root.left:
pathSum += root.left.val
if traverse(root.left):
return True
pathSum -= root.left.val
# return False # !!!
if root.right:
pathSum += root.right.val
if traverse(root.right):
return True
pathSum -= root.right.val
return False # !!!
if root == None:
return False
pathSum = root.val
return traverse(root)
-
DFS框架要注意在base case返回值進行“撤銷”操作从撼。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def traversal(root):
nonlocal pathSum
if root == None:
return False
pathSum += root.val
if root.left == None and root.right == None:
if pathSum == targetSum:
pathSum -= root.val
return True
else:
pathSum -= root.val # !!!
return False
valid_left = traversal(root.left)
if valid_left:
return True
valid_right = traversal(root.right)
if valid_right:
return True
pathSum -= root.val
return False
pathSum = 0
return traversal(root)
TBA
- 迭代，層序遍歷
- 入deque的時候把當前pathsum也加進去婆翔。
- 每一層popleft()出來node的時候判斷是否葉子節(jié)點拯杠。若是，則比較pathsum 和 targetsum.
TBA
- 思路
- example
- 類似上題啃奴，這里要找出所有可行答案潭陪。
- 回溯框架
- 復雜度. 時間：O(n), 空間: O(n)
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def traversal(root, pathsum):
if root.left == None and root.right == None:
if pathsum == targetSum:
res.append(path[:])
return
if root.left:
pathsum += root.left.val
path.append(root.left.val)
traversal(root.left, pathsum)
path.pop()
pathsum -= root.left.val
if root.right:
pathsum += root.right.val
path.append(root.right.val)
traversal(root.right, pathsum)
path.pop()
pathsum -= root.right.val
if root == None:
return []
res, path = [], [root.val]
traversal(root, root.val)
return res
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def traversal(root, path):
if root.left == None and root.right == None:
if sum(path) == targetSum:
res.append(path[:])
return
if root.left:
path.append(root.left.val)
traversal(root.left, path)
path.pop()
if root.right:
path.append(root.right.val)
traversal(root.right, path)
path.pop()
res = []
if root == None:
return res
path = [root.val]
traversal(root, path)
return res
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def traversal(root, pathSum):
if root.left == None and root.right == None:
if pathSum == targetSum:
res.append(path[:])
return
if root.left:
path.append(root.left.val)
traversal(root.left, pathSum+root.left.val)
path.pop()
if root.right:
path.append(root.right.val)
traversal(root.right, pathSum+root.right.val)
path.pop()
if root == None:
return []
res = []
path = []
path.append(root.val)
traversal(root, root.val)
return res
- 思路
- example
- 樹中每個node的值都不同，這樣可以用值唯一確定node.
- 遞歸構造樹最蕾。找出并建立樹的根節(jié)點依溯，然后劃分inorder和postorder數(shù)組，遞歸構造左子樹和右子樹瘟则，并且鏈接起來黎炉。這里的關鍵是找出切割位置（根節(jié)點），并且劃分左子樹和右子樹對應的兩個子數(shù)組醋拧。
- 構造樹（假設是最基本的三個元素的滿樹）：先建立根節(jié)點慷嗜。然后處理左節(jié)點和右節(jié)點前且鏈接起來。
- 例子：
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
- postorder（左右中）最右邊即為根節(jié)點
- inorder(左中右）需要線性掃描找到pivot位置丹壕，pivot左邊是左子樹 [9]庆械，pivot右邊是右子樹 [15,20,7]
- postorder左子樹取inorder左子樹相同size即可 [9]，postorder右子樹同理 [15,20,7]菌赖。
- 注意指標的取值范圍缭乘。
- 遞歸函數(shù)：參數(shù)為 當前節(jié)點，inorder, postorder琉用。
- 基本case: 注意有可能左或右子樹可能為空堕绩， 所以要處理[]情況策幼。
- 返回值：根節(jié)點
- 復雜度. 時間：O(n)?, 空間: O(n)
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
# len(inorder) == len(postorder)
# Base Case
if postorder == []:
return None
val = postorder[-1] # 根節(jié)點數(shù)值
root = TreeNode(val) # 建立節(jié)點
# Find pivot in inorder
pivot = 0
for i in range(len(inorder)):
if inorder[i] == val:
pivot = i
break
# partition inorder and postorder
# 左中右
# 左右中
inorder_left, inorder_right = inorder[:pivot], inorder[pivot+1:]
size_left, size_right = len(inorder_left), len(inorder_right)
postorder_left, postorder_right = postorder[:size_left], postorder[size_left : size_left+size_right]
# recursive and link
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
return root
- 可以“優(yōu)化”，傳遞inorder和postorder數(shù)組的start,end指標來確定左右子樹逛尚。
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
def traversal(start1, end1, start2, end2): # 1: inorder, 2: postorder
if start1 > end1:
return None
root_val = postorder[end2]
root = TreeNode(root_val)
# 分割
pivot_idx = 0
while pivot_idx <= end1:
if inorder[pivot_idx] == root.val:
break
pivot_idx += 1
left_size = pivot_idx - start1
root.left = traversal(start1, pivot_idx-1, start2, start2+left_size-1)
root.right = traversal(pivot_idx+1, end1, start2+left_size, end2-1)
return root
n = len(inorder)
return traversal(0, n-1, 0, n-1)
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
def build(inorder, postorder):
n = len(inorder)
if n == 0:
return None
root = TreeNode(postorder[-1])
val = postorder[-1]
idx = -1
for i in range(n):
if inorder[i] == val:
idx = i
break
root.left = build(inorder[0:idx], postorder[0:idx])
root.right = build(inorder[idx+1:n], postorder[idx:n-1])
return root
return build(inorder, postorder)
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
n = len(inorder)
if n == 0:
return None
val = postorder[-1]
root = TreeNode(val, None, None)
idx = 0
while idx < n:
if inorder[idx] == val:
break
idx += 1 # !!!
root.left = self.buildTree(inorder[:idx], postorder[:idx])
root.right = self.buildTree(inorder[idx+1:], postorder[idx:n-1])
return root
- 思路
- example
- 三生萬物垄惧，左中右的輪回
-
中前后
- 前中后
- 遞歸主體思路
- 建立節(jié)點
- 劃分兩個數(shù)組，分別得到左右子樹
- 遞歸調用建立左右子樹绰寞，鏈接
- 遞歸函數(shù)傳遞參數(shù): inorder, postorder 數(shù)組
- 基本case: 空節(jié)點
- 返回值：當前根節(jié)點
- 復雜度. 時間：O(n), 空間: O(n)
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
# preorder: 中左右
# inorder : 左中右
# Base Case
if len(preorder) == 0:
return None
val = preorder[0]
root = TreeNode(val)
# find pivot index in inorder
pivot = 0
for i in range(len(inorder)):
if inorder[i] == val:
pivot = i
break
# partition
inorder_left, inorder_right = inorder[:pivot], inorder[pivot+1:]
size_left, size_right = len(inorder_left), len(inorder_right)
preorder_left, preorder_right = preorder[1:1+size_left], preorder[1+size_left:]
# recursive, link
root.left = self.buildTree(preorder_left, inorder_left)
root.right = self.buildTree(preorder_right, inorder_right)
return root
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
n = len(inorder)
if n == 0:
return None
root = TreeNode(preorder[0])
val = preorder[0]
idx = -1
for i in range(n):
if inorder[i] == val:
idx = i
break
root.left = self.buildTree(preorder[1:idx+1], inorder[0:idx])
root.right = self.buildTree(preorder[idx+1:n], inorder[idx+1:n])
return root
