class Solution_iterative: def hasPathSum(self, root, target): stack = [(root, 0)] while stack: node, path = stack.pop() if node: if node.left is None and node.right is None and path + node.val == target: return True stack.extend([(node.left, path + node.val), (node.right, path + node.val)]) return False
def invertTree(self, root): stack = [root] while stack: node = stack.pop() if node: node.left, node.right = node.right, node.left stack += node.left, node.right return root
def BFS(root): if not root: return 0 prev,res=[root],[] while prev: cur=[] #给结果添加当前层数prev的平均值,prev为当前所有的值 val=sum([node.val for node in prev])/float(len(prev)) res.append(val) #该循环主要是cur添加prev所有的左右子树,即cur为下一层所有的值 while prev: node=prev.pop() if node.left: cur.append(node.left) if node.right: cur.append(node.right) #将当前层数变为下一层 prev=cur return res
def levelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ res=[] if not root: return [] prev=[root] while prev: temp=[node.val for node in prev] res.append(temp) cur=[] while prev: node=prev.pop(False) if node.left: cur.append(node.left) if node.right: cur.append(node.right) prev=cur return res
def findSecondMinimumValue(self, root): """ :type root: TreeNode :rtype: int """ if not root: return -1 prev=[root] minVal=root.val secondVal=float(‘inf‘) while prev: cur=[] while prev: node=prev.pop() if minVal<node.val and node.val<secondVal: secondVal=node.val if node.left: cur.append(node.left) if node.right: cur.append(node.right) prev=cur return -1 if secondVal==float(‘inf‘) else secondVal
def isBalanced(self, root): stack = [(0, root)] depth = {None: 0} while stack: seen, node = stack.pop() if node is None: continue if not seen: stack.extend([(1, node), (0, node.right), (0, node.left)]) else: if abs(depth[node.left] - depth[node.right]) > 1: return False depth[node] = max(depth[node.left], depth[node.right]) + 1 return True
原文:https://www.cnblogs.com/Lee-yl/p/9113870.html