題目簡介
110：平衡二叉樹
給定一個二叉樹菱阵，判斷它是否是高度平衡的二叉樹。
本題中缩功，一棵高度平衡二叉樹定義為：
一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1 晴及。
257：二叉樹的所有路徑
給你一個二叉樹的根節(jié)點 root ，按 任意順序 嫡锌，返回所有從根節(jié)點到葉子節(jié)點的路徑虑稼。
葉子節(jié)點 是指沒有子節(jié)點的節(jié)點蛛倦。
404：左葉子之和
初見思路
- 遞歸法，直接比較子樹的高度茸塞，大于1直接返回False，非常慢笋庄。
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def get_depth(root:Optional[TreeNode]) -> int:
if not root:
return 0
left_depth = get_depth(root.left)
if left_depth == -1: return -1
right_depth = get_depth(root.right)
if right_depth == -1: return -1
if abs(left_depth - right_depth) > 1:
return -1
return max(get_depth(root.left), get_depth(root.right)) + 1
return False if get_depth(root) == -1 else True
## 迭代法
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
height_map = {}
stack = [root]
while stack:
node = stack.pop()
if node:
stack.append(node)
stack.append(None)
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
else:
real_node = stack.pop()
left, right = height_map.get(real_node.left, 0), height_map.get(real_node.right, 0)
if abs(left - right) > 1:
return False
height_map[real_node] = 1 + max(left, right)
return True
257.用棧來迭代济丘，注意一個要點疟赊，棧在遞歸樹的時候入棧子節(jié)點先右后左近哟，出來的時候順序才會是左右。
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
stack, path_st, result = [root], [str(root.val)], []
while stack:
cur = stack.pop()
path = path_st.pop()
if not (cur.left or cur.right):
result.append(path)
if cur.right:
stack.append(cur.right)
path_st.append(path + '->' + str(cur.right.val))
if cur.left:
stack.append(cur.left)
path_st.append(path + '->' + str(cur.left.val))
return result
- 遞歸法很直觀
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
value = 0
if root.left and not (root.left.left or root.left.right):
value = root.left.val
return value + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
復(fù)盤思路
- 遞歸法還有更好的寫法
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root: return True
return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
self.isBalanced(root.left) and self.isBalanced(root.right)
def depth(self, root):
if not root: return 0
return max(self.depth(root.left), self.depth(root.right)) + 1
257的話還可以迭代回溯靠抑，參見回想錄的解法荠列。
重點難點
https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html
https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html
今日收獲
- 二叉進階
