Leetcode 513. 树左下角的值
讲解前：
直接看到这道题的时候先想到的就是直接用层序遍历搞定，返回最底层一层的第一个遍历到的数值就可以了
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
res = []
q = deque()
q.append(root)
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res[-1][0]讲解后：
在讲解的时候我其实也没有看完卡哥完整版的讲解，就发现其实卡哥的思路和我一开始想的一样，我就接着硬着头皮把这道题写出来了
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
res = 0
max_depth = float('-inf')
def dfs(root, depth):
nonlocal res
nonlocal max_depth
# base case is when we find a leaf node
# and check its depth to decide whether
# update the res value or not
if not root.left and not root.right:
if depth > max_depth:
res = root.val
# recursive case is to iterate through the tree
# and keep track of the depth, update the
# max depth first
max_depth = max(max_depth, depth)
if root.left:
dfs(root.left, depth + 1)
if root.right:
dfs(root.right, depth + 1)
dfs(root, 0)
return res这道题其实就是通过一个额外的变量来记录当前recursive call的深度，然后呢我们一直记录当前遍历过的最大深度，每当我们发现一个叶子节点并且他的深度大于之前遍历过的最大深度时，我们就让res 等于他
Leetcode 112. 路径总和：
讲解前：
这道题实在是有点麻烦，我总感觉能做出来但是写来写去很多bug
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
res = False
def dfs(root, s):
nonlocal res
# base case
if not root:
return False
# get the sum of including current node
sum_ = s + root.val
if sum_ == targetSum:
res = True
return res
# go to the left and right to see if we can
# find a node will help the route
# only do that when we have a left or right
# that can be added and stil not go beyond target
if root.left and sum_ + root.left.val <= targetSum:
left = dfs(root.left, sum_)
s = s - root.val
else:
left = False
if root.right and sum_ + root.right.val <= targetSum:
right = dfs(root.right, sum_)
s = s - root.val
else:
right = False
res = left or right
return res
dfs(root, 0)
return res这是一个可以ac的版本但是很烦人的一点就是，这道题是这样的，如果只有两个节点，那么我们就不能把单独的root当做路径来看待，所以哪怕root的值是target value也不行，但是如果确实没有节点只有一个root，又可以返回True
讲解后：
卡哥的对这道题的讲解非常好，而且我发现我其实读题的时候就读错了已经，这里我们只在乎从根节点到叶子节点的路径而不是任何路径都可以
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
# use dfs to iterate the tree
# have a count to keep track the sum
# including current root value
def dfs(root, count):
# base case is when we reached
# the leaf node and return if we have the target sum
if not root.left and not root.right:
return count == 0
# recursive case
if root.left:
if dfs(root.left, count - root.left.val):
return True
if root.right:
if dfs(root.right, count - root.right.val):
return True
return False
if not root:
return False
else:
return dfs(root, targetSum - root.val)这里卡哥用了一个很巧妙的想法就是通过对遍历的每一个节点进行减法，然后看是否能在leaf node的时候把targetsum 减成0来判断是否找到了路径，然后呢一开始的base case就很通俗易懂就是当我们找到一个leaf node的时候，直接return count是否为0，这里也同时说明了一点就是我们这里的count的值需要在上一层函数call 的时候，就帮我们已经减去了当前root的val，所以我们函数主体中比较的直接是count是否为0，而不用再减去lead node的val
然后呢在recursive cases中，我们需要在左右遍历的时候直接传入count - root.left/right.val 来达到上面说的效果，并且这里直接在传参的时候对count的值进行修改是一种隐藏的回溯，这意味着我们并没有改变当前函数中被传入进来的count 的值，这样当我们没有找到leaf node然后返回到一个节点开始遍历新的路径的时候，count的值还是保留在之前的值
然后呢因为我们直接对比count的值是否为0，这就需要我们在外面主函数体中做第一次调用的时候，直接就对count进行 targetsum - root.val 的操作，避免之后一个root节点并且root节点的值就是targetsum
Leetcode 106. 从中序后序遍历构造二叉树
讲解前：
这道题没什么思路，只有一点点印象之前学习二叉树的时候有过概念比如哪两种遍历顺序就能构造出树的整体并且是否唯一之类的
讲解后：
卡哥的讲解很到位，主要的思想就是反复的通过中序和后序遍历的特点来定义root节点和左右子树的区间，在第一次遍历的时候我们先检查后序数组中的最后一个元素，来确定当前树的根节点，拿到了根节点之后，去中序数组中找这个根节点所在的位置，然后就可以知道数组中这个根节点的左边所有元素都是左子树的元素，右边的都是右子树的元素
了解了这个特性之后我们明白了，利用同样的逻辑对于前序和中序遍历也是一样的，也可以构造出一颗唯一的二叉树，但是同时也明白了只知道前序和后序遍历是没办法构造唯一的二叉树的，因为前后序遍历能提供的信息都是根节点在哪里，可是完全没办法知道左右节点的分布情况，这也是为什么两棵树哪怕有完全一样的前序和后序遍历，也不能证明这两棵树完全一样
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
# 第一步: 特殊情况讨论: 树为空. (递归终止条件)
if not postorder:
return None
# 第二步: 后序遍历的最后一个就是当前的中间节点.
root_val = postorder[-1]
root = TreeNode(root_val)
# 第三步: 找切割点.
separator_idx = inorder.index(root_val)
# 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
inorder_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
# 第五步: 切割postorder数组. 得到postorder数组的左,右半边.
# ⭐️ 重点1: 中序数组大小一定跟后序数组大小是相同的.
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left): len(postorder) - 1]
# 第六步: 递归
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
# 第七步: 返回答案
return root
