【LeetCode 刷题】二叉树(3)-二叉树的属性

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为二叉树的属性相关的题目解析。

101. 对称二叉树

题目链接

class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:def traversal(L, R):if not L and not R:return Trueif not L or not R or L.val != R.val:return Falsereturn traversal(L.left, R.right) and traversal(L.right, R.left)return not root or traversal(root.left, root.right)

• 递归时，需要判断 L 和 R 两个节点，因此不能直接使用题目所给的函数（只有一个参数），而需另外创建 traversal(L, R)
• 分别递归 (L.left, R.right) 和 (L.right, R.left)

104.二叉树的最大深度

题目链接

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

• 深度优先遍历算法：后序遍历，因为需要先得到左、右子树的深度，才能够得到当前节点的深度；不用创建新的递归函数
• 广度优先遍历算法：见博客

111.二叉树的最小深度

题目链接

class Solution:def minDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0if not root.left:return self.minDepth(root.right) + 1if not root.right:return self.minDepth(root.left) + 1return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

• 深度优先遍历算法：后序遍历，但与上题不同，不能简单返回左右子树的 min，而需要特判左、右子树为空的情况；不用创建新的递归函数
• 广度优先遍历算法：见博客

222.完全二叉树的节点个数

题目链接

class Solution:def countNodes(self, root: Optional[TreeNode]) -> int:if root is None:return 0# 判断当前以当前节点为根结点的子树是否为满二叉树leftHeight, rightHeight = 0, 0leftPtr, rightPtr = root.left, root.rightwhile leftPtr:leftPtr = leftPtr.leftleftHeight += 1while rightPtr:rightPtr = rightPtr.rightrightHeight += 1if leftHeight == rightHeight:return pow(2, leftHeight + 1) - 1return self.countNodes(root.left) + self.countNodes(root.right) + 1

• 满二叉树节点数计算公式：$2^h-1$
• 判断是否为满二叉树的方式：左指针一直向左指，右指针一直向右指，如果两侧深度一样，则为满二叉树

110.平衡二叉树

题目链接

class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:def traversal(node: Optional[TreeNode]) -> int:if node is None:return 0left = traversal(node.left)if left == -1:return -1right = traversal(node.right)if right == -1:return -1if abs(left - right) <= 1:return max(left, right) + 1else:return -1return traversal(root) != -1

• 后序遍历+剪枝，剪枝操作通过特定的函数返回值来实现
• 如果左右子树高度差已经超过 1，则函数返回 -1；否则，正常返回子树高度

257. 二叉树的所有路径

题目链接

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:path, res = [], []def traversal(node: Optional[TreeNode]) -> None:if node is None:returnpath.append(str(node.val))if not node.left and not node.right:res.append('->'.join(path))else:traversal(node.left)traversal(node.right)path.pop()traversal(root)return res

• 先序遍历，先把当前节点放入 path，之后递归处理左右节点
• 不能在 if node is None: 判断内部收集答案（会重复收集），而应该在叶子节点的位置收集

404.左叶子之和

题目链接

class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:res = 0def traversal(node: Optional[TreeNode]):nonlocal resif node is None:returnif node.left and not node.left.left and not node.left.right:res += node.left.valtraversal(node.left)traversal(node.right)traversal(root)return res

• 判断左叶子的逻辑需要在左叶子结点的上一层
• nonlocal 表示外部嵌套函数内的局部变量变量

513.找树左下角的值

题目链接

class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:maxDepth, res = 0, 0def traversal(node: Optional[TreeNode], depth: int):nonlocal maxDepth, resif node is None:returntraversal(node.left, depth + 1)if depth > maxDepth:maxDepth = depthres = node.valtraversal(node.right, depth + 1)traversal(root, 1)return res

• 深度优先遍历：中序或后序遍历均可（要保证第一个访问的是"左"），之后正常遍历整棵树，并记录目前最大深度；左下角节点肯定为第一个到达最大深度的节点
• 层序遍历：遍历到最后一层找最左侧节点（更直观）

112. 路径总和

题目链接

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if root is None:return FalsetargetSum -= root.valif not root.left and not root.right:return targetSum == 0return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

• 到达叶节点时，判断 targetSum == 0