代码随想录算法训练营Day17

110. Balanced Binary Tree

!!! 平衡二叉树的左右子树仍为平衡二叉树.

A height balanced binary tree is a binary tree in which the height of the left subtree and right subtree of any node does not differ by more than 1 and both the left and right subtree are also height balanced.

关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准（毕竟要在这上面刷题）。

遇到的问题:因为在递归过程中,需要比较深度,同时还要传出True or False. 不知如何让其协调.

class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:def depthBalanced(root: TreeNode) -> int:if not root: return 0dLeft = depthBalanced(root.left)if dLeft == -1: return -1 # 错在这一步dRight = depthBalanced(root.right)if dRight == -1: return -1if abs(dLeft - dRight)> 1:return -1else:return max(dLeft, dRight)+1if not root: return Truereturn False if depthBalanced(root) == -1 else True# TC: O(N)# SC: O(N)

257. Binary Tree Paths

终止条件 不需要判断 root == None

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:# 后序递归# 条件指出root非空res = []def path(root: TreeNode, s: str):if not(root.left or root.right): res.append(s)if root.right:             path(root.right,s + "->"+str(root.right.val))if root.left:           path(root.left, s + "->"+str(root.left.val))returnpath(root, str(root.val))return res# TC: O(N)# SC: O(N)

前序迭代

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:# 前序迭代res = []stack = []cur = rootpath = str(root.val)stack.append((cur, path))while stack:cur, path = stack.pop()if not(cur.left or cur.right):res.append(path)if cur.right: stack.append((cur.right, path+"->"+str(cur.right.val)))if cur.left: stack.append((cur.left, path+"->"+str(cur.left.val)))return res

404. Sum of Left Leaves

Sol1 层序迭代

class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:# 层序迭代if not root: return 0q = [root]res = [] # save the value of all leaveswhile q:for _ in range(len(q)):cur = q.pop(0)if cur.left: q.append(cur.left)if not(cur.left.left or cur.left.right): res.append(cur.left.val)if cur.right: q.append(cur.right)return sum(res)

Sol2 前序递归

        # Sol2 前序递归if not root: return 0if not(root.left or root.right): return 0sum = 0if root.left and not(root.left.left) and not(root.left.right):sum += root.left.valsum += self.sumOfLeftLeaves(root.left)sum += self.sumOfLeftLeaves(root.right)return sum