110.平衡二叉树
1、递归法
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if self.get_height(root) != -1: # -1 代表高度差大于 1
return True
else:
return False
def get_height(self, root):
if root is None:
return 0
# 左
left_height = self.get_height(root.left)
if left_height == -1:
return -1
# 右
right_height = self.get_height(root.right)
if right_height == -1:
return -1
# 中
res = abs(left_height-right_height)
if res > 1: # 实际高度差大于 1 , 标记不是平衡二叉树了。
return -1
else: # 平衡二叉树求实际高度
return 1 + max(left_height, right_height)
2、迭代法
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
st = []
if root:
st.append(root)
height_map = {}
while st:
node = st.pop()
if node:
# 中
st.append(node)
st.append(None)
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
else:
node = st.pop()
left, right = height_map.get(node.left, 0), height_map.get(node.right, 0)
if abs(left-right) > 1:
return False
height_map[node] = 1 + max(left, right)
return True
257. 二叉树的所有路径
1、递归回溯法
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res = []
if root is None:
return res
path = []
self.dfs(root, path, res)
return res
def dfs(self, root, path, res):
# 中
path.append(str(root.val))
if not root.left and not root.right:
res.append("->".join(path))
return
# 左
if root.left:
self.dfs(root.left, path, res)
path.pop() # path 是公共的，需要回溯
# 右
if root.right:
self.dfs(root.right, path, res)
path.pop()
2、隐藏递归法
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res = []
if root is None:
return res
path = "" # 赋值路径
self.dfs(root, path, res)
return res
def dfs(self, root, path, res):
path += str(root.val)
if not root.left and not root.right:
res.append(path)
return
if root.left:
self.dfs(root.left, path + "->", res)
if root.right:
self.dfs(root.right, path + "->", res)
404.左叶子之和
思路：什么是左叶子节点
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
if not root.left and not root.right:
return 0
left_val = self.sumOfLeftLeaves(root.left) # 左
if root.left and not root.left.left and not root.left.right:
left_val = root.left.val
right_val = self.sumOfLeftLeaves(root.right) # 右
sum_left = left_val + right_val # 中
return sum_left