代码随想录算法训练营第十七天 |110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和
最新回答
指尖星光在流浪
2026-05-20 14:58:15
核心思路：判断二叉树是否平衡，需计算每个节点的左右子树高度差是否超过1。采用自底向上的递归方法，若发现不平衡子树立即返回-1，避免重复计算。
代码解析：
- cal_height函数递归计算树高，若左右子树高度差>1或任一子树不平衡（返回-1），则当前树也不平衡。
- isBalanced调用cal_height，结果非-1即为平衡。
关键点：
- 提前终止：发现不平衡立即返回-1，提升效率。
- 高度计算：树高=max(左高, 右高)+1。
核心思路：递归遍历所有路径，从根节点到叶子节点，拼接路径字符串。
代码解析：
- 递归终止条件：当前节点为叶子节点（左右子节点均为空），返回该节点值的字符串。
- 递归处理左右子树，将当前节点值与子路径用"->"连接。
- 合并左右子路径列表返回。
关键点：
- 路径拼接：每次递归在子路径前添加当前节点值。
- 叶子判断：仅当左右子节点均为空时才视为叶子节点。
核心思路：递归计算所有左叶子节点的值之和。左叶子定义为父节点的左子节点且自身无子节点。
代码解析：
- 递归终止条件：空节点返回0。
- 处理左子树时，若左子节点是叶子节点，直接取其值；否则递归计算左子树。
- 递归处理右子树。
- 返回左右子树结果之和。
关键点：
- 左叶子判断：root.left存在且无左右子节点。
- 累加逻辑：左叶子值直接累加，非叶子节点递归处理。
- 平衡二叉树：通过高度差判断，递归时优化提前终止。
- 所有路径：深度优先搜索，路径字符串拼接。
- 左叶子之和：区分左叶子与普通左节点，递归累加。
三题均采用递归方法，核心在于明确递归终止条件与子问题的处理逻辑。平衡树关注高度差，路径问题注重字符串拼接，左叶子和则需准确识别左叶子节点。
热门标签
