蓝桥15

浅浅的花香味﹌ 2023-01-12 01:45 158阅读 0赞

# 一二的幂次 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]

*  无语，一开始我想一直×2去%，直到大于2，看来题解学了个简单的思路
 *  如果n一直除以2.那么最终结果肯定能从2的幂变成1，否则就是其他数
 *  提示：python不会省小数，3/2=1.5,C中是1

class Solution:
        def isPowerOfTwo(self, n: int) -> bool:
            while n>1:
                n=n/2
            return n==1

# 二235二叉搜索数的最近公共搜索祖先： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]

*  二叉搜索数是中序遍历从小到大的排序，所以我们可以根据root节点的数值大小和qp的数值大小比较
 *  如果root大小大于qp，向左left传递
 *  如果root大小小于pq，向有right传递
 *  直到第一个在中间的数字节点，就是结果

class Solution:
        def lowestCommonAncestor(self, root, p, q):
            while root:
                if root.val > p.val and root.val > q.val:
                    root = root.left
                elif root.val < p.val and root.val < q.val:
                    root = root.right
                else:
                    return root

# 三236二叉树的最近公共祖先 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]

*  二叉数的话我们对于搜索算法，包括深搜广搜，原理都是左右节点的递归回溯
 *  这道题我们使用深搜算法并回溯
 *  我们对于root存在并且不为qp的节点向下递推，分为左递推，右递推，如果root，左节点，右节点中有q和p就返回root
 *  对于root不存在和root为p或q的就直接返回
 *  其他情况返回q或p

class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            if not root:
                return None
            if root==p or root==q:
                return root
            l=self.lowestCommonAncestor(root.left,p,q)
            r=self.lowestCommonAncestor(root.right,p,q)
            if (p in [root,l,r]) and(q in [root,r,l]): 
                return root
            elif not l and not r:
                return None
            else:
                return l or r

## 但是根据结果![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 3]   效果有些差，我们学习题解思路再改进一下： ##

*  改进1：我们不判断左中右三节点是否包含qp，我们判断左右子树是否为空，如果都存在，就返回root，如果存在一个就返回一个，这样的递归更快

class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            if not root: return root
            if root.val == p.val or root.val == q.val: return root
            l = self.lowestCommonAncestor(root.left, p, q)
            r = self.lowestCommonAncestor(root.right, p, q)
            if l and r: return root
            elif l or r:
            	return l or r

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 4]  
明显快了一些

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]: /images/20221119/4d0f3c9fb4264d4ca1d88b1f2202176f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]: /images/20221119/e75e00f5e0bb41a882daf2fa43b78b23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]: /images/20221119/35ef1d00bd56419dba68c16a62808feb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 3]: /images/20221119/74f9abd211364f51a34c65de43e59e91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 4]: /images/20221119/daecf7e4a45946699be3f8e4a27525c6.png