104. 二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
1 | 3 |
返回它的最大深度 3 。
1 | class Solution: |
101. 对称二叉树
给你一个二叉树的根节点 root
, 检查它是否轴对称。
示例 1:
1 | 输入:root = [1,2,2,3,4,4,3] |
1 | class Solution: |
226. 翻转二叉树
给你一棵二叉树的根节点 root
,翻转这棵二叉树,并返回其根节点。
1 | 输入:root = [4,2,7,1,3,6,9] |
1 | class Solution: |
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。注意:叶子节点 是指没有子节点的节点。
1 | 输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 |
1 | class Solution: |
113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。
1 | 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 |
1 | class Solution: |
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
示例 1:
1 | 输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 |
示例 2:
1 | 输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 |
分析:设 lca_node 为节点 p、q 的最近公共祖先。则 lca_node 只能是下面几种情况:
- p、q 在 lca_node 的子树中,且分别在 lca_node 的两侧子树中。
- p = lca_node,且 q 在 lca_node 的左子树或右子树中。
- q = lca_node,且 p 在 lca_node 的左子树或右子树中。
具体思路为:
- 如果当前节点 node 为 None,则说明 p、q 不在 node 的子树中,不可能为公共祖先,直接返回 None。
- 如果当前节点 node 等于 p 或者 q,那么 node 就是 p、q 的最近公共祖先,直接返回 node
- 递归遍历左子树、右子树,并判断左右子树结果。
- (1). 如果左子树为空,则返回右子树。
- (2). 如果右子树为空,则返回左子树。
- (3). 如果左右子树都不为空,则说明 p、q 在当前根节点的两侧,当前根节点就是他们的最近公共祖先。
- (4). 如果左右子树都为空,则返回空。
1 | class Solution: |
297. 二叉树的序列化与反序列化
设计一个算法,来实现二叉树的序列化与反序列化。
分析:
序列化:将二叉树转为字符串数据表示。按照前序递归遍历二叉树,并将根节点跟左右子树的值链接起来(中间用 ,
隔开)。注意:如果遇到空节点,则标记为 ‘None’,这样在反序列化时才能唯一确定一棵二叉树。
反序列化:将字符串数据转为二叉树结构。先将字符串按 ,
分割成数组。然后递归处理每一个元素。
- 从数组左侧取出一个元素。
- 如果当前元素为 ‘None’,则返回 None。
- 如果当前元素不为空,则新建一个二叉树节点作为根节点,保存值为当前元素值。并递归遍历左右子树,不断重复从数组中取出元素,进行判断。
- 最后返回当前根节点。
1 | class Codec: |