代码随想录算法训练营第十六天|leetcode513.找树左下角的值、leetcode112.路径总和、leetcode106.从中序与后序遍历序列构造二叉树、leetcode105. 从前序与中序遍

1 leetcode513.找树左下角的值

题目链接：513. 找树左下角的值 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：怎么找二叉树的左下角？ 递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值_哔哩哔哩_bilibili

思路：就是用一个东西存储result，使用后续遍历，如果遇到了最深的那一个值，就进行向前保存，但是不知道如何下手

1.1 视频后的思路

这道题可以用递归和迭代，但是我已经忘了迭代怎么用了

1.1.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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.maxdepth =float('-inf')
        self.result = 0
        self.traversal(root,0)
        return self.result
    def traversal(self,node,depth):
        if node.left==None and node.right == None:
            if depth>self.maxdepth:
                self.maxdepth = depth
                self.result = node.val
            return
        if node.left:
            depth +=1
            self.traversal(node.left,depth)
            depth-=1
        if node.right:
            depth +=1
            self.traversal(node.right,depth)
            depth -=1
        return

1.1.2 迭代的思路

好久没写真的忘了这个题应该怎么写了，但是写的时候就是越看越会了

from collections import deque
# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if root==None:
            return 0
        queue = deque()
        queue.append(root)
        result = 0
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if i == 0:
                    result = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

1.2 本题小结

1. 这道题目的递归，其实怎样遍历都行，主要是结束的条件需要判断好，如果这个层是最大层，在对这个值进行返回就好了
2. 迭代的方法，是用队列，然后判断i==0的时候进行一个输出，不断覆盖最后找到结果

2 leetcode112.路径总和

题目链接：112. 路径总和 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：拿不准的遍历顺序，搞不清的回溯过程，我太难了！ | LeetCode：112. 路径总和_哔哩哔哩_bilibili

思路：这道题我想的是用前序遍历，然后对数值进行相加，得到一个result,如果遇到比这个大的值，就进行删除，否则一直加到最后，如果加到最后没找到，向上返回一层的操作，就这样，如果找到了就返回True，否则就是false

2.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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root ==None:
            return False
        return self.traversal(root,targetSum-root.val)
    def traversal(self,node,count):
        if node.left ==None and node.right ==None and count==0:
            return True
        if node.left ==None and node.right ==None and count!=0:
            return False
        if node.left:
            count -= node.left.val
            if self.traversal(node.left,count):
                return True
            count +=node.left.val
        if node.right:
            count -= node.right.val
            if self.traversal(node.right,count):
                return True
            count += node.right.val
        return False

2.2 本题小结

1. 递归的神奇之处就在于我看懂了题目，但是我做的时候还是会一塌糊涂，做不好，呜呜呜呜呜呜，等这一期跟完，我就知道哪些薄弱点了，下期继续刷
2. 题目思路就是一直往下找，找到了但是遇到了一个不符合的值，再加，不断操作，，，

3 leetcode106.从中序与后序遍历序列构造二叉树

题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：坑很多！来看看你掉过几次坑 | LeetCode：106.从中序与后序遍历序列构造二叉树_哔哩哔哩_bilibili

思路：没思路的一道题，自己把自己绕晕了属于是

3.1 视频后的思路

思路：

1. 终止条件：树为空
2. 后序遍历最后一个节点就是中间节点
3. 找到切割点
4. 对前序数组和后续数组切割
5. 递归传参数
6. 返回答案

# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(postorder) == 0:
            return None
        rootvalue = postorder[-1]
        root = TreeNode(rootvalue)
        if len(postorder) == 1:
            return root
        ind = 0
        for i in range(len(inorder)):
            if inorder[i] == rootvalue:
                ind = i
                break
        inorder_left = inorder[:ind]
        inorder_right = inorder[ind+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

这是一个自己看代码看笑的题目

3.2 类似题目来一个

题目链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0:
            return None
        root_val = preorder[0]
        root = TreeNode(root_val)
        if len(preorder) == 1:
            return root
        ind = 0
        for i in range(len(inorder)):
            if inorder[i]== root_val:
                ind =i
                break
        inorder_left = inorder[:ind]
        inorder_right = inorder[ind+1:]
        preorder_left = preorder[1:len(inorder_left)+1]
        preorder_right = preorder[len(inorder_left)+1:len(preorder)]
        root.left = self.buildTree(preorder_left,inorder_left)
        root.right = self.buildTree(preorder_right,inorder_right)
        return root

3.3 本题小结

1. 这道题目的思路就是如何找到中间节点，如果将这个值找到了就知道了，通过递归就可以把其他位置进行一个返回的操作
2. 然后就是如何从一个已知的位置找另一个节点呢，这个地方也会迷惑，但是仔细在纸上画一下就会好很多

4 今日小结

1. 第一道题目，迭代是很容易的，就是定义一个队列，然后不断找，将第一个值返回给result，循环就好。
2. 第一题中的递归也是不错的思路，这个地方就是很巧妙，定义了一个深度，就是如果有比这个更深的深度，就返回，然后对左右子树都递归；还有一个就是定义一个无限小的深度，这样递归有大的就可以赋值给他，不断比较
3. 第二题，再次接触回溯，这道题的思路很巧妙的一点，就是定义了一个总和，如果能找到一条路径那就返回True，否则就是False
4. 第三题，开始是没有思路的，后来听了视频前面，就豁然开朗了，开始就明白了怎么去写，虽然这次展示的代码还是有点多，希望下次会好一点