110.平衡二叉树

问题

题目链接：https://leetcode.cn/problems/balanced-binary-tree/
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
示例：
在这里插入图片描述

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

解答

这里强调一波概念：

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

先用递归写一个返回最大深度的函数，然后再用递归判断根节点的左右子树是否相差大于1.

# 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 maxnode(self, root):if not root: return 0return 1+max(self.maxnode(root.left), self.maxnode(root.right))def isBalanced(self, root: Optional[TreeNode]) -> bool:if not root:return Truea = abs(self.maxnode(root.left) - self.maxnode(root.right))if a > 1:return Falsereturn self.isBalanced(root.left) and self.isBalanced(root.right)

随想录上的解答：

class Solution:def isBalanced(self, root: TreeNode) -> bool:if self.get_height(root) != -1:return Trueelse:return Falsedef get_height(self, root: TreeNode) -> int:# Base Caseif not root:return 0# 左if (left_height := self.get_height(root.left)) == -1:return -1# 右if (right_height := self.get_height(root.right)) == -1:return -1# 中if abs(left_height - right_height) > 1:return -1else:return 1 + max(left_height, right_height)

class Solution:def isBalanced(self, root: TreeNode) -> bool:return self.height(root) != -1def height(self, node: TreeNode) -> int:if not node:return 0left = self.height(node.left)if left == -1:return -1right = self.height(node.right)if right == -1 or abs(left - right) > 1:return -1return max(left, right) + 1

此处用了python3.8的海象表达式（walrus operator）： if (left_height := self.get_height(root.left)) == -1:
海象表达式（Walrus operator）是Python 3.8版本引入的一种新的语法特性。它使用了:=这个符号，允许在表达式中进行变量的赋值操作。

通常情况下，Python中的变量赋值是在等号的左侧进行的，例如x = 10。而海象表达式允许我们在表达式的右侧进行变量赋值，将结果赋给一个新的变量。这对于简化代码和增加可读性非常有用。
一个常见的用法是在条件语句中，例如：

if (n := len(my_list)) > 10:print(f"List length is {n} which is greater than 10.")

在上面的代码中，海象表达式(n := len(my_list))用于同时计算列表的长度并将结果赋值给变量n。然后，我们可以直接在条件语句中使用变量n进行比较操作。
海象表达式还可以在其他情况下使用，例如循环语句和列表推导式中，以简化代码和提高可读性。
需要注意的是，海象表达式是在Python 3.8版本中引入的新特性，因此在较旧的Python版本中不可用。在使用海象表达式时，需要确保代码运行在支持该特性的Python版本上。

迭代思路也类似，先用一个函数求最大高度，然后采用栈模拟后续遍历判断每个节点的子树是否平衡。
当然此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。

class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:if not root:return Trueheight_map = {}stack = [root]while stack:node = stack.pop()if node:stack.append(node)stack.append(None)if node.left: stack.append(node.left)if node.right: stack.append(node.right)else:real_node = stack.pop()left, right = height_map.get(real_node.left, 0), height_map.get(real_node.right, 0)if abs(left - right) > 1:return Falseheight_map[real_node] = 1 + max(left, right)return True

257. 二叉树的所有路径

问题

题目链接：https://leetcode.cn/problems/binary-tree-paths/
给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。

叶子节点是指没有子节点的节点。
示例：
在这里插入图片描述

输入：root = [1,2,3,null,5]
输出：[“1->2->5”,“1->3”]

解答

自己想这题的时候思路很简单，递归只需要判断是否为叶子节点就行，不是叶子节点则进入下一层，即该节点的子节点。但会遇到一个问题，那就是如何复制已存在的路径，看了解答才知道可以用copy package，那么题目就很简单了。

# 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
# copy可以用来复制路径，避免对上一级的path产生影响
import copyclass Solution:def markpath(self, root, path, result):if not root: return Nonepath.append(root.val)if not root.left and not root.right:result.append('->'.join(map(str, path))) #map(fucntion, iteratable)if root.left:self.markpath(root.left, copy.copy(path), result)if root.right:self.markpath(root.right, copy.copy(path), result)# copy函数是复制了一个path，而不是在原path上修改，因此回不回溯都不影响#path.pop()def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:if not root: return []result = []self.markpath(root, [], result)return result

但是由于python里有copy库，因此是否回溯就不重要了，因为永远不会对上一级的path产生影响，所以以下补上C++里的方法，帮助更好理解回溯

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

前序遍历以及回溯的过程如图：
在这里插入图片描述

在这里插入图片描述
与python里不同，c++没有copy函数复制path，因此需要采用一个vector来记录path，所以要把vector 结构的path转为string格式，再把这个string 放进 result里。同时当遇到叶子节点的时候，即递归结束，要开始回溯了，方法就是删除path最后一个元素。同时要注意，回溯和递归是一一对应的，有一个递归，就要有一个回溯，即递归要和回溯在同一个括号内。

class Solution {
private:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 // 这才到了叶子节点if (cur->left == NULL && cur->right == NULL) {string sPath;for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return;}if (cur->left) { // 左 traversal(cur->left, path, result);path.pop_back(); // 回溯}if (cur->right) { // 右traversal(cur->right, path, result);path.pop_back(); // 回溯}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;traversal(root, path, result);return result;}
};

补充：
python其实也可以不用copy函数，同样可以与c++对应，修改如下：

from typing import List, Optionalclass Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:if not root:return []result = []self.generate_paths(root, [], result)return resultdef generate_paths(self, node: TreeNode, path: List[int], result: List[str]) -> None:path.append(node.val)if not node.left and not node.right:result.append('->'.join(map(str, path)))if node.left:self.generate_paths(node.left, path, result)path.pop()if node.right:self.generate_paths(node.right, path, result)path.pop()

再修改一下：
from typing import List, Optional

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:if not root:return []result = []self.generate_paths(root, [], result)return resultdef generate_paths(self, node: TreeNode, path: List[int], result: List[str]) -> None:path.append(node.val)if not node.left and not node.right:result.append('->'.join(map(str, path)))if node.left:self.generate_paths(node.left, path, result)#path.pop()if node.right:self.generate_paths(node.right, path, result)#path.pop()path.pop()

模拟一下下图的过程吧：
在这里插入图片描述

首先定义一下：if1，if2，if3分别表示generate_paths里的三个判断if，以及下文的第几个递归表示序号行执行的递归，不表示实际递归层数。

cur=1，path=[1]，满足if2，进入if2的下一层递归2
cur=2，path=[1，2]，满足if2，进入if2的下一层递归3
cur=3，path=[1，2，3]，满足if1，输出路径，且不满足if2，if3，因此第3个递归执行结束
第3个递归执行完毕，回到第2个递归，执行剩下的path.pop()，path=[1,2]
但此时第2个递归还没结束，因为也满足if3
cur=2，path=[1，2]，满足if3，进入if3的下一层递归
cur=4，path=[1，2，4]，满足if2，进入if2的下一层递归
cur=5，path=[1，2，4，5]，满足if1，输出路径
第8个递归执行完毕，回到上一层递归，即第7个递归，执行剩下的pop，path=[1,2,4]
cur=4，path=[1，2，4]，满足if3，进入if3的下一层递归
cur=6，path=[1，2，4，6]，满足if1，输出路径
第11个递归执行结束，退回到第10个，执行剩下的pop，path=[1,2,4]
由于第10个递归if3也判断完毕，因此第10个递归执行结束，退回上一层即第6，执行pop，path=[1,2]
同理第6也执行完毕，退回到第1个，执行pop，path=[1]
cur=1，path=[1]，满足if3，进入if3的下一层递归，之后的右子树同理，输出path=[1,7,8]后不断回溯到第1个迭代，由于此时cur=root=1的左右节点都处理完了，因此整个递归过程结束。

顺便用chatGPT解释了一下为啥要path.pop()：
在给左子树递归调用 generate_paths 之后，需要回溯到上一层继续遍历其他分支。由于 path 列表是作为参数传递的，如果不进行回溯操作，那么左子树的遍历过程中添加的节点值将会一直保留在 path 列表中，影响到右子树的遍历。

通过调用 path.pop()，可以在递归回溯到上一层时，将 path 列表中的当前节点值移除，恢复到上一层的状态。这样，在处理右子树时，就能够从一个空的 path 列表开始，不受之前遍历过的节点的影响。

简而言之，path.pop() 的作用是确保在回溯到上一层时，将当前节点从路径列表中移除，以便在处理其他分支时得到正确的路径。

404.左叶子之和

问题

题目链接：https://leetcode.cn/problems/sum-of-left-leaves/
计算给定二叉树的所有左叶子之和。
示例：
在这里插入图片描述

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

解答

这道题目要求左叶子之和，其实是比较绕的，因为不能判断本节点是不是左叶子节点。此时就要通过节点的父节点来判断其左孩子是不是左叶子了。
此时有两个判断条件，首先该节点没有子节点，然后该节点是上一个节点的左节点。因此判断停止条件是not root.left.left and not root.left.right。但是停止之后返回什么呢，肯定不能只返回root.left.val，因为如果该root存在右节点，我们并没有对右节点的进行判断，因此我们将root.right作为下一层的root继续输入，因此我们要返回root.left.val+function(root.right)

# 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 0# 排除没有左节点的情况，但是右节点没判断# 因此我们返回右子树的所有左叶子的和if not root.left: return self.sumOfLeftLeaves(root.right)# 同理，右节点没判断，因此加上右子树的所有左叶子和if (not root.left.left) and (not root.left.right):return root.left.val + self.sumOfLeftLeaves(root.right)return self.sumOfLeftLeaves(root.left)+self.sumOfLeftLeaves(root.right)

用chatGPT解释了一下上述代码：
这段代码实现了计算二叉树中所有左叶子节点值的和。下面是代码的解释：

1.首先，检查根节点是否为空，如果为空，表示当前子树为空树，直接返回0作为和的初始值。

2.然后，检查根节点的左子节点是否为空，如果为空，表示当前子树没有左子树，那么就递归地计算右子树中的左叶子节点值的和（通过调用 self.sumOfLeftLeaves(root.right)）。

3.如果根节点的左子节点存在，再进一步检查左子节点是否为叶子节点（即没有左子节点和右子节点）。如果是叶子节点，那么将左子节点的值加上右子树中左叶子节点值的和，作为最终的和。

4.如果根节点的左子节点不是叶子节点，那么就递归地计算左子树和右子树中左叶子节点值的和，并将两者的和返回。

这段代码利用了递归的思想，通过不断地将问题拆分成更小的子问题来求解。它按照以下步骤计算左叶子节点值的和：

如果当前子树为空树，则和为0。
如果当前子树没有左子树，则计算右子树中的左叶子节点值的和。
如果当前子树有左子树，并且左子节点为叶子节点，则将左子节点的值加上右子树中左叶子节点值的和，作为最终的和。
如果当前子树有左子树，并且左子节点不是叶子节点，则分别计算左子树和右子树中左叶子节点值的和，并将两者的和返回。
通过递归地处理每个节点，直到遍历完整棵二叉树，最终得到所有左叶子节点值的和作为结果返回。

随想录上的结构更清晰一些：

class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:if not root:return 0# 检查根节点的左子节点是否为叶节点if root.left and not root.left.left and not root.left.right:left_val = root.left.valelse:left_val = self.sumOfLeftLeaves(root.left)# 递归地计算右子树左叶节点的和right_val = self.sumOfLeftLeaves(root.right)return left_val + right_val

迭代法思路一样，只不过用循环和栈实现：

class Solution:def sumOfLeftLeaves(self, root: TreeNode) -> int:"""Idea: Each time check current node's left node. If current node don't have one, skip it. """stack = []if root: stack.append(root)res = 0while stack: # 每次都把当前节点的左节点加进去. cur_node = stack.pop()if cur_node.left and not cur_node.left.left and not cur_node.left.right: res += cur_node.left.valif cur_node.left: stack.append(cur_node.left)if cur_node.right: stack.append(cur_node.right)return res