代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二叉搜索树中的众数、leetcode236. 二叉树的最近公共祖先

标签：第十八天 None right val self 二叉搜索 root left

1 leetcode530.二叉搜索树的最小绝对差

视频链接：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树_哔哩哔哩_bilibili

思路：定义一个极大值作为结果，然后在中序遍历过程中进行比较出结果

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 __init__(self):
        self.pre = None
        self.result = float('inf')
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return
        left = self.getMinimumDifference(root.left)
        if self.pre !=None and abs(self.pre.val-root.val)<self.result:
            self.result = abs(self.pre.val-root.val)
        self.pre = root
        right = self.getMinimumDifference(root.right)
        return self.result

1.2 视频的代码

看了以后发现自己的代码可以浅优化一下，优化了一步，运行速度有提高，其他的没变化

# 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 __init__(self):
        self.pre = None
        self.result = float('inf')
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return
        left = self.getMinimumDifference(root.left)
        if self.pre !=None:
            self.result = min(self.result,abs(self.pre.val-root.val))
        self.pre = root
        right = self.getMinimumDifference(root.right)
        return self.result

1.3 暴力搜索方法

# 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 __init__(self):
        self.vec = []
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        vec = self.vec
        self.traversal(root)
        if len(vec)<2:
            return 0
        result = float('inf')
        for i in range(len(vec)-1):
            result = min(result,abs(vec[i]-vec[i+1]))
        return result
    def traversal(self,node):
        if node == None:
            return
        self.traversal(node.left)
        self.vec.append(node.val)
        self.traversal(node.right)

1.4 本题小结

本题思路和之前验证一棵树是不是二叉搜索树的方法一模一样，所以就是按照指针方法就去写了，最后发现答案和我所想的也是一模一样的
其他的没有特别难的地方吧

2 leetcode501.二叉搜索树中的众数

题目链接：501. 二叉搜索树中的众数 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数_哔哩哔哩_bilibili

思路：想用一个数组去顺序存储二叉树的数值，然后将数组进行一个键值对的计算，键为数组的值，值为出现的次数，最后返回值最大的数

2.1 自己的代码

这个版本听冗余的，但是几个自己出错的点学会了

找键对应的最大值，可以直接使用max(dic.values())
使用键值循环的时候，用的是for key,value in dic.items()

# 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 __init__(self):
        self.vec = []
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        vec = self.vec
        self.traversal(root)
        dic = dict()
        for i in range(len(vec)):
            dic[vec[i]] = dic.get(vec[i],0)+1
        result = []
        maxval = max(dic.values())
        for k,v in dic.items():
            if v ==maxval:
                result.append(k)
        return result

    def traversal(self,node):
        if node is None:
            return
        self.traversal(node.left)
        self.vec.append(node.val)
        self.traversal(node.right)

2.2 看视频后的思路

很多时候很难想到到底要不要几个值，还有最大值我该怎么给？就是在这两个地方卡壳了，没有用这种方式写出来代码

2.2.1 定义一个新函数

写错的原因：

忘记给self.pre=cur

# 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 __init__(self):
        self.pre = None
        self.count = 0
        self.maxcount = 0
        self.result = []
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        self.traversal(root)
        return self.result
    def traversal(self,cur):
        if cur == None:
            return
        self.traversal(cur.left)
        if self.pre == None:
            self.count = 1
        elif self.pre.val == cur.val:
            self.count +=1
        else:
            self.count = 1

        if self.count == self.maxcount:
            self.result.append(cur.val)

        if self.count >self.maxcount:
            self.maxcount = self.count
            self.result = []
            self.result.append(cur.val)
        self.pre = cur
        self.traversal(cur.right)

2.2.2 直接在主函数进行

# 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 __init__(self):
        self.pre = None
        self.count = 0
        self.maxcount = 0
        self.result = []
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return
        self.findMode(root.left)
        if self.pre == None:
            self.count = 1
        elif self.pre.val == root.val:
            self.count +=1
        else:
            self.count = 1

        if self.count == self.maxcount:
            self.result.append(root.val)

        if self.count >self.maxcount:
            self.maxcount = self.count
            self.result = []
            self.result.append(root.val)
        self.pre = root
        self.findMode(root.right)
        return self.result

2.3 本题小结

注意中序遍历最后需要将值root赋值过去，这里写错了
一个很巧妙的办法就是对数据进行判断，这里我真的没想到，看完视频后才发现这个办法真的很巧妙；附上代码

if self.count == self.maxcount:
    self.result.append(root.val)

if self.count >self.maxcount:
    self.maxcount = self.count
    self.result = []
    self.result.append(root.val)

3 leetcode236. 二叉树的最近公共祖先

题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先_哔哩哔哩_bilibili

思路：好的，这是一个我看都看不懂的题目，更别说来写这道题目了

3.1 视频后的思路

突然发现自己做题目，真的分析的不够深，就是手头看了一下，不知道怎么写就有种放弃了，但是听完视频以后我可以完全独立写完整个代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == None:
            return root
        if root==p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left!=None and right != None:
            return root
        elif left==None and right != None:
            return right
        elif left!=None and right ==None:
            return left
        else:
            return None

3.2 本题小结

从这道题很明显感受就是我对遍历的选择，用什么方式掌握的不是很牢固，所以会有经常出错的时候，但是每次看完视频讲解以后，我就会有一种豁然开朗的感觉
但是这里想说一下自己的进步吧，感觉到这个时候我的迭代方法是真的慢慢理解了，为什么会有这个，为什么要去使用，，，

4 今日小结

这里面前两道题其实延续了十七天的内容，所以理论上都是非常简单的，尝试一下就会出结果
主要困难的地方在于第三题，我没理解真的没理解这个值的前一个怎么返回，后来发现不断向上传递就是一个非常不错的办法就可以解决了
真不错，虽然这一天也是补的打卡，但是我一次性补了两天的内容，很棒

标签：第十八天,None,right,val,self,二叉,搜索,root,left
From： https://www.cnblogs.com/csfy0524/p/18531043