110. 平衡二叉树
- 思路
example
-
平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
每个节点的左右子树高度差 <= 1
每个节点的左右子树最大深度差 <= 1
-
两个要点：
- 每个子树都是平衡的
- 左右子树分别平衡，并且左子树最大深度 与 右子树最大深度 的差不超过1
修改最大深度代码。后序遍历。如果当前节点左右子树不平衡，返回-1作为标记。
最后返回值如果不等于-1，说明是平衡的。
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def traversal(root): # 计算以root为根节点的二叉树的最大深度
if root == None:
return 0
leftMaxDept = traversal(root.left) # 或者叫leftHeight
if leftMaxDept == -1:
return -1
rightMaxDept = traversal(root.right)
if rightMaxDept == -1:
return -1
if abs(leftMaxDept - rightMaxDept) > 1:
return -1
else:
return max(leftMaxDept, rightMaxDept) + 1
flag = traversal(root)
if flag == -1:
return False
else:
return True
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def traversal(root):
if root == None:
return 0, True
left_h, left_valid = traversal(root.left)
if not left_valid:
return -1, False
right_h, right_valid = traversal(root.right)
if not right_valid:
return -1, False
if abs(left_h - right_h) > 1:
return -1, False
return max(left_h, right_h) + 1, True
height, valid = traversal(root)
return valid
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def traversal(root):
if root == None:
return True, 0
valid_left, height_left = traversal(root.left)
valid_right, height_right = traversal(root.right)
if valid_left == False or valid_right == False:
return False, max(height_left, height_right)+1
if abs(height_left - height_right) <= 1:
return True, max(height_left, height_right)+1
else:
return False, max(height_left, height_right)+1
res, height = traversal(root)
return res
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def traverse(root):
if root == None:
return True, 0
res_left, h_left = traverse(root.left)
res_right, h_right = traverse(root.right)
h = max(h_left, h_right) + 1
if res_left == False or res_right == False:
return False, h
if abs(h_left - h_right) > 1:
return False, h
return True, h
res, h = traverse(root)
return res
257. 二叉树的所有路径
- 思路
- example
- 前序遍历 （自上而下），递归，dfs, 回溯（隐）
- 这个情况前序比较自然。
- 复杂度. 时间：O(n), 空间: O(n)
关键：最后叶子节点的判断
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
if root == None:
return []
res = []
path = ''
self.traversal(root, path, res)
return res
def traversal(self, root, path, res):
path += str(root.val)
if root.left == None and root.right == None: # 叶子节点
res.append(path)
if root.left:
self.traversal(root.left, path + '->', res)
if root.right:
self.traversal(root.right, path + '->', res)
return
- 稍微不同写法 （可以更清晰的看到回溯过程）
- 先调用递归，再把节点加进path
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traversal(root):
if root == None:
return
path.append(str(root.val))
if root.left == None and root.right == None:
res.append('->'.join(path))
traversal(root.left)
traversal(root.right)
path.pop()
res = []
path = []
traversal(root)
return res
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traversal(root):
if root == None:
return
path.append(str(root.val))
if root.left == None and root.right == None:
res.append('->'.join(path))
path.pop() # !!!
return
traversal(root.left)
traversal(root.right)
path.pop()
res = []
path = []
traversal(root)
return res
- “改进版”，使用dummyhead方便统一处理
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traversal(root):
if root.left == None and root.right == None: # 叶子节点
res.append('->'.join(path))
if root.left:
path.append(str(root.left.val))
traversal(root.left)
path.pop()
if root.right:
path.append(str(root.right.val))
traversal(root.right)
path.pop()
return
dummyhead = TreeNode(-1, root, None)
if dummyhead.left == None:
return []
res = []
path = []
traversal(dummyhead)
return res
- 先加节点加进path,再调用递归
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traverse(root):
if root == None:
return
if root.left == None and root.right == None:
res.append('->'.join(path))
return
if root.left:
path.append(str(root.left.val))
traverse(root.left)
path.pop()
if root.right:
path.append(str(root.right.val))
traverse(root.right)
path.pop()
res = []
path = [str(root.val)]
traverse(root)
return res
- 后序遍历也可以，自下而上
TBA
404. 左叶子之和
- 思路
- example
- 叶子，左叶子
- 判断左叶子：当前节点只能判断是否叶子。进一步判断左叶子需要parent节点。如果不想维护parent节点标记的话，可以提早判断（i.e., 遍历节点当作parent节点，直接往下搜索两代判断左孩子是否左叶子。
- 根节点本身不算作左叶子节点。
- 后序遍历，递归
- 注意分情况讨论
left_sum + right_sum + left_leave (左子树的左节点正好是叶子节点）
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
left_sum = self.sumOfLeftLeaves(root.left) # 以root.reft为根节点左叶子之和 (root.left.val不会被计算在内)
right_sum = self.sumOfLeftLeaves(root.right) # 以root.right为根点左叶子之和
# 还有一种情况：root.left是左叶子
if root.left and root.left.left == None and root.left.right == None:
left_leave = root.left.val
else:
left_leave = 0
return left_sum + right_sum + left_leave
-
前序遍历
- 标记当前节点类型：是左孩子还是右孩子。
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def traversal(root, child_type):
nonlocal res
if root == None:
return
if root.left == None and root.right == None: # 叶子节点
if child_type == 'left':
res += root.val
return
traversal(root.left, 'left')
traversal(root.right, 'right')
# dummyhead = TreeNode(-1)
# dummyhead.right = root
res = 0
traversal(root, 'right') # root is the right-child
return res
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def traversal(root, child_type):
nonlocal res
if root == None:
return
if root.left == None and root.right == None:
if child_type == 'left':
res += root.val
return
traversal(root.left, 'left')
traversal(root.right, 'right')
res = 0
traversal(root, 'None')
return res
- 不用标记
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def traverse(root):
nonlocal res
if root == None:
return
if root.left:
if root.left.left == None and root.left.right == None:
res += root.left.val
traverse(root.left)
if root.right:
traverse(root.right)
res = 0
traverse(root)
return res
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def traverse(root):
nonlocal res
if root == None:
return
if root.left == None and root.right == None:
return
if root.left == None:
traverse(root.right)
return # !!!
if root.left.left == None and root.left.right == None:
res += root.left.val
traverse(root.right)
return # !!!
traverse(root.left)
traverse(root.right)
res = 0
traverse(root)
return res
