代码随想录算法训练营第十五天|110、平衡二叉树 257、二叉树的所有路径 404、左叶子之和 222、完全二叉树的节点个数

目录110. 平衡二叉树题目描述解题思路257. 二叉树的所有路径题目描述解题思路404. 左叶子之和题目描述解题思路222. 完全二叉树的节点个数题目描述解题思路小结题目描述给定一个二叉树判断它是否是 平衡二叉树解题思路计算高度超过了就将全局变量变为Falseclass Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: flag True def depth(node): nonlocal flag if node None: return 0 leftdepth depth(node.left) rightdepth depth(node.right) if abs(leftdepth - rightdepth) 1: flag False return max(leftdepth,rightdepth) 1 depth(root) return flag用-1表示已经不是平衡二叉树class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: def getHeight(node): if node None:return 0 leftHeight getHeight(node.left) if leftHeight -1:return -1 rightHeight getHeight(node.right) if rightHeight -1:return -1 if abs(leftHeight - rightHeight) 1:return -1 else: return max(leftHeight,rightHeight) 1 return False if getHeight(root) -1 else True257. 二叉树的所有路径题目描述给你一个二叉树的根节点root按任意顺序返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。解题思路首先本我采用递归方法按照题意从中间节点开始输出故采用前序遍历即前左右其次传入的参数根节点遍历一条路径时的数组结果数组第三递归终止条件当前节点为叶子节点的时候终止当前递归并将一条路径的数组添加到结果数组中最后当左右节点一次递归完成需要将之前的节点pop特别注意的是将数组转化为字符串并用特定符号连接map(str,path)将path中的每一个元素都转化为str相当于str(x) for x in pathclass Solution: def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]: def travesal(node,path,result): path.append(node.val) if node.left None and node.right None: result.append(-.join(map(str,path))) if node.left: travesal(node.left,path,result) path.pop() if node.right: travesal(node.right,path,result) path.pop() result [] path [] travesal(root,path,result) return resultmap的用法map(函数可迭代对象)函数可以自定义也可以如上面所示转换类型404. 左叶子之和题目描述给定二叉树的根节点root返回所有左叶子之和。解题思路遍历二叉树采用前序遍历传入二叉树的根节点计算并传出total和当前节点为空时返回0题目目标找出左叶子节点判断他是左节点并且该节点为叶子节点class Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) - int: if not root: return 0 def getsum(node): total 0 if node None: return 0 if node.left and not node.left.left and not node.left.right: total node.left.val total getsum(node.left) total getsum(node.right) return total return getsum(root)222. 完全二叉树的节点个数题目描述给你一棵完全二叉树的根节点root求出该树的节点个数。完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层从第 0 层开始则该层包含1~ 2h个节点。解题思路先处理当前节点采用前序遍历传入root根节点当前节点为空时返回0无数据不为空时给当前子树的节点数设为1递归遍历子树计算相加左子树节点数和右子树节点数返回result为当前子树的节点数class Solution: def countNodes(self, root: Optional[TreeNode]) - int: def travesal(node): result 0 if node None: return 0 result 1 result travesal(node.left) result travesal(node.right) return result return travesal(root)小结使用递归三部曲根据题意如果先处理当前节点则用前序遍历如果先处理左右节点则用后序遍历尽量使用返回值累加不依赖外部变量对于int/str/bool---函数内不可变对于list/dict/对象---可直接修改遍历二叉树的时间复杂度都是O(n)空间复杂度都是O(n)递归调用栈栈的深度 树的高度为什么递归会调用栈每次调用递归函数系统会把当前这一层的函数暂存在内存中等子函数回来每多一层递归内存就多一层