代码随想录算法训练营day12（二叉树）

平衡二叉树

• https://leetcode.cn/problems/balanced-binary-tree/

思路

• 什么是平衡二叉树：左子树的高度与右子树的高度相差不超过1
• isBalanced用来判断是否为平衡二叉树，如果当前树不是平衡二叉树，直接返回最终结果False。如果当前树为平衡二叉树，就再判断其左右子树，左右子树也必须为平衡二叉树
• cal_depth用来求一个子树的最大深度，这是之前讲过的内容（求最大深度、最小深度、节点个数，都是基础内容）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def cal_depth(self,root):cur = rootif not cur:return 0leftHeight = self.cal_depth(cur.left)rightHeight = self.cal_depth(cur.right)height = 1 + max(leftHeight, rightHeight)return heightdef isBalanced(self, root: Optional[TreeNode]) -> bool:if not root:return Trueleft_depth = self.cal_depth(root.left)    # 求出左子树的深度right_depth = self.cal_depth(root.right)   # 求出右子树的深度if abs(left_depth - right_depth) > 1:    # 相差return Falsereturn self.isBalanced(root.left) and self.isBalanced(root.right)

二叉树的所有路径

• https://leetcode.cn/problems/binary-tree-paths/

思路

• 这道题是使用回溯来求解，第一次接触回溯法，多看看视频来理解。

具体写法

• 递归的写法里传入三个参数：（1）当前处理的节点；（2）当前的路径；（3）总的结果集
• 递归的终止条件：当节点为叶子节点时，把当前路径加入结果集
• 递归的单层处理：当node有左节点时，递归处理左节点，处理结束后回溯。当node有右节点时，递归处理右节点，处理结束后回溯

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def travel(self, node, path, res):if not node.left and not node.right:   # node为叶子节点path = [str(x) for x in path]res.append('->'.join(path))   # 将某一条路径加入到总的结果集当中if node.left:  # 左有值path.append(node.left.val)self.travel(node.left, path, res)path.pop() # 某一条路线递归结束后，弹出if node.right:  # 右有值path.append(node.right.val)self.travel(node.right, path, res)path.pop()  # 某一条路径递归结束后，弹出def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:cur = rootif not cur:return []res = []   # 记录所有路径path = [cur.val]  # 记录当前路径self.travel(cur,path, res)return res

左叶子之和

• https://leetcode.cn/problems/sum-of-left-leaves/description/

思路

• 使用后序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:if not root:  # 终止条件，当前节点为空return 0if not root.left and not root.right:  # 终止条件，当前节点是叶子节点return 0left_num = self.sumOfLeftLeaves(root.left)right_num = self.sumOfLeftLeaves(root.right)cur_num = 0if root.left and not root.left.left and not root.left.right: # # root.left 是左叶子cur_num = root.left.val     # 记录左叶子的值return cur_num + left_num + right_num  # 三部分的汇总

完全二叉树的节点个数

• https://leetcode.cn/problems/count-complete-tree-nodes/description/

思路

• 把完全二叉树当成二叉树去计算，使用后序遍历去计算

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def countNodes(self, root: Optional[TreeNode]) -> int:cur = rootif not cur:return 0left_num = self.countNodes(cur.left)right_num = self.countNodes(cur.right)result = left_num + right_num + 1   # 核心return result