每日leetcode

Python相关技巧

dict() # 实现哈希表
enumerate() # 用于将一个可遍历的数据对象组合为一个索引序列，同时列出数据和数据下标
<ele> in <dict> # 判断元素是否为字典的键
divmod(<除数>, <被除数>) # 得到元组(<商>, <余数>)
if <变量> # 等效于 if <变量> != None (如果变量有实值)
if not <变量> # 等效于 if <变量> == None (如果变量无实值)

数组

1. 两数之和

数组的暴力循环

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return []

66. 加一

加法器本位与进位问题。注意C++ vector容器的使用。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int add = 1;
        int sum = 0;
        vector<int> res(digits.size());

        for(int i = digits.size() - 1; i >= 0 ; i--){
            sum = digits[i] + add;
            res[i] = sum % 10; // 本位
            add = sum / 10; // 进位
        }

        if(add > 0){
            res.insert(res.begin(), add);
        }

        return res;
    }
};

118. 杨辉三角

注意C++ vector容器二维数组的使用。

杨辉三角是二项式系数在三角形中的一种几何排列。递推式为 $C_{n}^{i} = C_{n-1}^{i-1} + C_{n-1}^{i}$。

class Solution {
public:
    vector<vector<int>> generate(int numRows) { 
        vector<vector<int>> res(numRows);
        for(int i = 0; i < res.size(); i++) { 
            res[i].resize(i + 1); 
            res[i][0] = 1;
            res[i][res[i].size() - 1] = 1;
            for(int j = 1; j < res[i].size() - 1; j++){
                res[i][j] = res[i-1][j-1] + res[i-1][j];
            }
        } 
        return res;
    }
};

119. 杨辉三角 II

空间优化，滚动数组。

由于每一行杨辉三角都只取决于前一行，因此可以只用两个数组

$cur[0] = cur[-1] = 1$

$cur[k] = pre[k-1] + pre[k]$

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> pre,cur;
        for(int i = 0; i <= rowIndex; i++) { 
            cur.resize(i+1);
            cur[0] = cur[i] = 1;
            for(int j = 1; j < i; j++){
                cur[j] = pre[j-1] + pre[j];
            }
            pre = cur;
        }
        return cur;
    }
};

空间优化，单数组。

在单个数组中从后至前更新元素 $row[j] += row[j - 1]$

例如 rowIndex = 3 时，

初始化：0 0 0 0 -> 1 0 0 0

1. i = 1：j = 1：1 1 0 0
2. i = 2：j = 2：1 1 1 0 -> j = 1：1 2 1 0
3. i = 3：j = 3：1 2 1 1 -> j = 2：1 2 3 1 -> j=1：1 3 3 1

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for(int i = 1; i <= rowIndex; i++) { 
            for(int j = i; j > 0; j--){
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};

时间优化，将相邻行的递推式转为行内相邻元素的递推式。注意通过 1LL 将 int 转为 long long。

根据 $C_{n}^{m}=\frac{n!}{m!(n-m)!}$，可得 $C_{n}^{m}=\frac{n-m+1}{m}C_{n}^{m-1}$

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;
        }
        return row;
    }
};

链表

快慢指针

快慢指针常用来解决链表环问题，因为在链表中使用两个速度不同的指针时：

1. 如果没有环，快指针将停在链表的末尾。
2. 如果有环，快指针最终将与慢指针相遇。

设置指针速度的一个安全的选择是，每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 $M$，经过 $M$ 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

使用链表快慢指针的题常常也能用哈希表解。

141. 环形链表

使用快慢指针判断链表是否为环形的关键在于：

1. 快慢指针初始位置的设置
2. 循环终止条件① 快慢指针相遇
3. 循环终止条件② 快指针到达链表末端

注意，在运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # 快慢指针初始位置: 头节点
        slow = head
        fast = head
		
        # 外部循环终止条件: 快指针到达链表末端
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 内部循环终止条件: 快慢指针相遇
            if slow == fast:
                return True
        return False 

142. 环形链表 II

使用快慢指针找到环链表入口节点，需要借助其中的数学规律：

1. 无环：快指针到达链表末端

2. 有环：快慢指针相遇，相遇时，有以下步数关系

   设链表共有 $a+b$ 个节点，其中链表头部到链表入口有 $a$ 个节点（不计链表入口节点）， 链表环有 $b$ 个节点；设两指针分别走了 $f，s$ 步，则有：

   1. fast 走的步数是 slow 步数的 $2$ 倍，即 $f=2s$；（fast 每轮走 2 步、slow 每轮走 1 步）
   2. fast 比 slow 多走了 $n$ 个环的长度，即 $f=s+nb, n=1,2,...$；（ 双指针相遇时 fast 比 slow 多走环长整数倍）；

   由上式可得，$f=2nb,s=nb$（fast和 slow 分别走了 $2n，n$ 个环长）

从头节点到达入口节点的步数可以是 $a, a+nb$，已知相遇点处 slow 的步数为 $nb$，未知 $a$。

我们再次使用双指针控制 $a$，得到 $a+nb$ ：

1. 指针① （原快指针）指向头节点，指针②（原慢指针）指向相遇节点，双指针速度均为 1
2. 双指针相遇时，指针①走了 $a$ 步，指针②走了 $a+nb$ 步，相遇节点即为入口节点

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def second_cycle(slow, fast, head):
            # 双指针找寻入口节点 
            fast = head
            # 双指针相遇处为入口节点，包含a=0的情况
            while fast != slow:
                slow = slow.next
                fast = fast.next
            return slow     

        slow = head
        fast = head       
		# 外部循环终止条件: 快指针到达链表末端
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 内部循环终止条件: 快慢指针相遇
            if slow == fast:
                return second_cycle(slow, fast, head)
        return None

160. 相交链表

反转链表

双链表

双指针

11. 盛最多水的容器

盛水面)积：

$S(i,j)=(i-j)\times min(h[i]-h[j])$

初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1 变短：

• 若向内 移动短板 ，水槽的短板 min(h[i], h[j]) 可能变大，因此下个水槽的面积可能增大 。

• 若向内 移动长板 ，水槽的短板 min(h[i], h[j]) 不变或变小，因此下个水槽的面积 一定变小 。

便于理解，实例展示

# 别人的代码
class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res
    
## 涉及到结果取最值用min/max

# 我的代码
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        right = len(height) - 1
        left = 0
        area = 0
        while left != right:
            new_area = (right - left) * min(height[left], height[right])
            if new_area > area:
                area = new_area
            if height[left] < height[right]:
                left += 1
                continue
            if height[left] >= height[right]:
                right -= 1
                continue
        return area

27. 移除元素

双游标i ，j 实现数组元素移除。

游标j 指向新数组当前索引，游标i 指向新数组需要被填入的元素索引。

当游标i元素与val相同时，游标j 停止后移一次（当前游标i指向元素被删除）。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int j = 0;
        for(int i = 0; i < nums.size() ; i++){
            if(nums[i] != val){
                nums[j] = nums[i];
                ++j;
            }
        }
        return j;
    }
};

26. 删除有序数组中的重复项

数组有序，你 双游标i ，j 实现数组元素移除。

前游标j ，后游标i 。

当后游标元素与前游标不同时，前游标后移并赋值为后游标（值未改变）；

当后游标元素与前游标相同时，前游标停止后移一次（当前后游标指向元素被删除）。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int j = 0;
        for(int i = 1; i < nums.size() ; i++){
            if(nums[i] != nums[j]){
                nums[++j] = nums[i];
            }
        }
        return j + 1;
    }
};

167. 两数之和 II - 输入有序数组

数组有序的1. 两数之和，可使用双指针

和11. 盛最多水的容器很像，用双指针实现缩减搜索空间

初始化左右指针分别位于有序数组头尾

• 当指针元素之和大于target，右指针-1
• 当指针元素之和小于target，左指针+1

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = 0
        right = len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                return [left+1,right+1]
            if s > target:
                right -= 1
            if s < target:
                left += 1
        return []

15. 三数之和

滑动窗口

滑动窗口问题主要有以下四步：

1. 定义需要维护的变量
2. 定义滑动窗口的双指针
3. 更新滑动窗口和需要维护的变量

最重要的是理清更新滑动窗口的逻辑！！！

定值滑动窗口

643. 子数组最大平均数 I

这是一个长度为定值k的滑动窗口问题，可以维护双指针求解

当右指针超出定值长度时，每次右指针右移一位时，左指针都左移一位，以保证滑动窗口长度一定

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
       # 1. 定义需要维护的变量
        suma, max_avg = 0, -float('inf')
        # 2. 定义滑动窗口的双指针
        left = 0
        for right in range(len(nums)):
            # 3. 更新滑动窗口
            suma += nums[right]
            if right - left + 1 > k:
                suma -= nums[left]
                left += 1
            # 4. 更新需要维护的变量
            if right - left + 1 == k:
                max_avg = max(max_avg, suma / float(k))
        return max_avg

## python正无穷float('inf')/负无穷-float('inf')

长度为定值时也可以指维护单指针，另一指针由单指针和定长k计算得到

class Solution(object):
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        sums = 0
        largest = float('-inf')
        for i, num in enumerate(nums):
            sums += num
            if i >= k:
                sums -= nums[i - k]
            if i >= k - 1:
                largest = max(sums, largest)
        return largest / float(k)

不定值滑动窗口

字符串+滑动窗口

3. 无重复字符的最长子串

维护队列作为滑动窗口

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        ls = []
        left, sub_len, max_len = 0, 0, 0
        for right,cha in enumerate(s):
            # 当右指针存在重复字符，删除队列首字符至无重复字符
            while cha in ls:
                del(ls[0])
                sub_len -= 1
                
            ls.append(cha)
            sub_len += 1
            max_len = max(sub_len, max_len)
        return max_len
 
## 列表在此起队列作用，新字母添加在尾部(ls.append())，从头部删除(del(ls[0]))

更多滑动窗口的题

查找表

哈希表

1. 两数之和

遍历得到x1，x2，求解x1 + x2是否等于target

遍历得到x1，以x1值为键，索引为值存入哈希表，

并对于每个x1，查询哈希表中是否存在为target - x1的键，取出其值

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

## dict() 实现哈希表
## enumerate() 用于将一个可遍历的数据对象组合为一个索引序列，同时列出数据和数据下标
## <ele> in <dict> 判断元素是否为字典的键

202. 快乐数

这题与找数学规律有关，任何数字在进行快乐数检验时，有 $3$ 种可能：

1. 最终会得到 1
2. 最终会进入无限循环
3. 最终会进入无限不循环

这个数学规律的关键点在于，探索是否存在循环规律。

1. 所有的数都会在有限次数的转化中变成小于243的数。

位数	最大数	平方和
1	9	81（81*1）
2	99	162（81*2）
3	999	243 （81*3）

对于 $k$ 位数，其值的范围为 $10^{k-1} \sim 10^k-1$，值最大时有平方和最大值 $81 \times k$，$k=1,2,3,...$ 。

易得，当 $k>3$ 时，恒有 $81 \times k < 10^{k-1}$，所以任意位数大于 $3$ 的数平方和的位数都会逐渐降低，直至 $243$ 内。

2. 非快乐数最终都在特定循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 内。

通过枚举 $1 \sim 243$ 的数可以得到如上规律

得到以上数学规律后，我们明确快乐数检验只有两种可能：

1. 最终会得到 1
2. 最终会进入无限循环

因此，我们使用哈希表存储每次得到的平方和，并认为，出现重复的数字即进入无限循环~~(目前并没有搞懂为什么)~~。

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        def get_sum(n):
            result = 0
            # 得到每一位数的平方和
            # divmod(<除数>, <被除数>) 得到元组 (<商>, <余数>)
            while n > 0:
                n, digit = divmod(n, 10)
                result += digit**2
            return result

        results = list()
        # n==1: 是快乐数
        # n in <哈希表>: 不是快乐数，进入循环
        while n != 1 and n not in results:
            results.append(n)
            n = get_sum(n)
        return n == 1

二分查找

完全有序

34. 在排序数组中查找元素的第一个和最后一个位置

子问题：返回有序数组中第一个$\ge target$ 的数的位置；若所有数都$< target$，返回数组长度。

使用二分查找解决这个子问题的基本思路：

1. 数组的元素有不确定、$\ge target$、$< target$三种状态，每次将不确定状态的元素将纳入二分查找区间
2. 确定初始不确定状态元素的范围，根据选区的区间，确定左指针和右指针
3. 每次取中位元素(left + right) // 2与$target$ 比较，一半区间将更新为$\ge target$或$< target$状态，重新划定二分查找区间
4. 根据左指针/右指针结束循环时的位置，判断最终取值

因此，需要关注以下几点：

1. 数组元素的状态： if nums[m] < target

2. 左指针/右指针的初始值，与对应区间：l = 0 r = len(nums) - 1 # 闭区间 [left, right]

3. 根据单元素区间的情况，确定二分查找的循环条件：while l <= r: # l=r时为单元素区间nums[l](nums[r])

4. 判断不确定状态的数组元素，区间上下限更新，与左右指针的替换：l = m + 1 # 新区间 [mid+1, right] r = m - 1 # 新区间 [left, mid-1]

5. 最终结果取左指针/右指针：return l

   当返回有序数组中第一个$\ge target$ 的数的位置时，状态为不确定、$\ge target$、$< target$。

   因此，闭区间[left, right]中，左指针l的左边恒$< target$，右指针r的右边恒$\ge target$，因此l/r-1是$\ge target$的第一个数的位置。

def lower_bound1(nums, target):
    # 闭区间 [left, right]
    l = 0
    r = len(nums) - 1
    while l <= r: # l=r时为单元素区间nums[l](nums[r])
        m = (l + r) // 2
        if nums[m] < target:
            l = m + 1 # 新区间 [mid+1, right]
        else:
            r = m - 1 # 新区间 [left, mid-1]
    return l

def lower_bound2(nums, target):
    # 左闭右开区间 [left, right)
    l = 0
    r = len(nums)
    while l < r: # l<r时为单元素区间nums[l]
        m = (l + r) // 2
        if nums[m] < target:
            l = m + 1 # 新区间 [mid+1, right)
        else:
            r = m # 新区间 [left, mid)
    return l # left/right

def lower_bound3(nums, target):
    # 开区间 (left, right)
    l = -1
    r = len(nums)
    while l+1 < r: # # l+1<r时为单元素区间nums[l+1]
        m = (l + r) // 2
        if nums[m] < target:
            l = m # 新区间 (mid, right)
        else:
            r = m # 新区间 (left, mid)
    return r

本题可转化为两次求解子问题。即：

1. $target$的第一个位置：lower_boud(nums, target)
2. $target$的最后一个位置：lower_boud(nums, target+1) - 1

由于子问题是返回有序数组中第一个$\ge target$ 的数的位置；若所有数都$< target$，返回数组长度。

因此，求$target$的第一个位置时需要判断：

1. 此数是否$=target$：返回有序数组中第一个$\ge target$ 的数的位置
2. 是否为数组长度：所有数都$< target$

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        start = lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        end = lower_bound(nums, target+1) - 1
        return [start, end]

35. 搜索插入位置

本题即求有序数组中第一个$\ge target$ 的数的位置；若所有数都$< target$，返回数组长度。是 34. 在排序数组中查找元素的第一个和最后一个位置 的子问题。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 闭区间 [left, right]
        l = 0
        r = len(nums) - 1
        while l <= r: # l=r时为单元素区间nums[l](nums[r])
            m = (l + r) // 2
            if nums[m] < target:
                l = m + 1 # 新区间 [mid+1, right]
            else:
                r = m - 1 # 新区间 [left, mid-1]
        return l

69. x 的平方根

本题与前几题相比，条件发生了变化。即求有序数组中最后一个$\le target$ 的数。

由于算术平方根都是正整数，将左右指针的初始值分别设为1、x，中值为 (而非中值的位置) m = (l + r) // 2。

由题意，数组的元素有不确定、$> target$、$\le target$三种状态。

结束循环时，左指针l的左边恒$\le target$，右指针r的右边恒$> target$，右指针r停在左指针l的左边。

因此l-1/r是最后一个$\le target$ 的数。

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l = 1
        r = x
        while l <= r: 
            m = (l + r) // 2
            if m*m <= x:
                l = m + 1
            else:
                r = m - 1 
        return r # l-1

局部有序

162. 寻找峰值

本题使用二分查找的关键也是：

1. 确定三种状态

   不确定、为目标峰顶左侧、为目标峰顶或其右侧

2. 判断数组元素初始状态，确定左右指针

   [-1] 元素为目标峰顶或其右侧，其他元素不确定

3. 确定二分查找的表达式，与对应状态

   将中间元素m 与m+1比较，nums[m] < nums[m+1] 为目标峰顶左侧，nums[m] >= nums[m+1] 为目标峰顶或其右侧

4. 判断循环结束时，左右指针的状态，确定最终取值

   左指针左侧为目标峰顶左侧，右指针右侧为目标峰顶或其右侧，右指针停在左指针左侧

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 0 
        r = len(nums) - 2
        while l <= r:
            m = (l + r) // 2
            if nums[m] < nums[m+1]:
                l = m + 1
            else:
                r = m - 1
        return l # r+1

153. 寻找旋转排序数组中的最小值

二叉树

DFS子树递归

递归时主要确定：

1. 递的主体和判断
2. 归的边界条件

104. 二叉树的最大深度

如果我们知道了左子树和右子树的最大深度 l和 r，那么该二叉树的最大深度即为max(l,r) + 1。而左子树和右子树的最大深度又可以以同样的方式递归计算：

1. 递的主体：左子树深度l、右子树深度r
2. 递的判断：最大深度为max(l,r) + 1
3. 归的边界条件：在访问到空节点时退出

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 归的边界条件
        if root is None:
            return 0
        else:
            # 递的主体和判断
            return max(self.maxDepth(root.right), self.maxDepth(root.left)) + 1
## 递归调用self.function_name()
        
## 也可以维护全局变量实现递归
## nonlocal 声明某函数内的非局部、非全局变量
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, cnt):
            if node is None:
                return
            cnt += 1
            nonlocal ans
            ans = max(ans, cnt)
            dfs(node.left, cnt)
            dfs(node.right, cnt)
        dfs(root, 0)
        return ans

100. 相同的树

判断二叉树是否相同，就是不断递归判断左右子树是否相同：

1. 递的主体：左子树是否相同self.isSameTree(p.left, q.left)、右子树是否相同self.isSameTree(p.right, q.right)
2. 递的判断：树相同 <= 左子树相同、右子树相同、本节点值相同
3. 归的边界条件：在一树访问到空节点(若此时两树均为空节点为true、否则为false)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # 归的边界条件
        if p is None or q is None:
            return p is q
        # 递的主体和判断
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

101. 对称二叉树

判断二叉树是否轴对称，就是不断递归判断左右子树是否满足轴对称条件。

1. 递的主体：p左子树与q右子树isSy(p.left, q.right)、p右子树与q左子树isSy(p.right, q.left)
2. 递的判断：树轴对称 <= 左子树与右子树相同、右子树与左子树相同、本节点值相同
3. 归的边界条件：在一树访问到空节点(若此时两树均为空节点为true、否则为false)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
#  哦莫！第一次自己写出来还一次过的！
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        p = root.left
        q = root.right
        def isSy(p,q):
            if p is None or q is None:
                return p is q
            return p.val == q.val and isSy(p.left, q.right) and isSy(p.right, q.left)
        return isSy(p,q)

110. 平衡二叉树

平衡二叉树的每个节点的左右子树的高度差的绝对值不超过 1，判断二叉树是否平衡，就是不断递归判断左右子树是否满足平衡条件。

1. 递的主体：左子树是否平衡self.isBalanced(root.left)、右子树是否平衡self.isBalanced(root.right)
2. 递的判断：树平衡 <= 左子树平衡、右子树平衡、本节点处左右两子树高度差绝对值不超过1(高度计算需要调用另一递归函数)
3. 归的边界条件：访问到空节点(返回true)

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode  
        :rtype: bool
        """
        if root is None:
            return True
        def height(node):
            if node is None:
                return 0
            return max(height(node.left), height(node.right)) + 1
        return abs(height(root.left)-height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

199. 二叉树的右视图

BFS层序遍历

广度优先搜索(BFS) 层序遍历时，维护队列，每次搜索队首节点的子节点添加至队尾，并移除此节点。

102. 二叉树的层序遍历

广度优先搜索(BFS)在层序遍历的场景下极为适用，通常维护一个队列，将当层节点加入队列、上层节点移出队列来实现BFS。

107. 二叉树的层序遍历 II只需将结果反转即可。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        res = []
        que = [root]
        while que:
            res.append([node.val for node in que])
            # 维护队列实现BFS
            new_que = []
            for node in que:
                if node.left:
                    new_que.append(node.left)
                if node.right:
                    new_que.append(node.right)
            que = new_que
        return res

199. 二叉树的右视图

右视图中只含有每层最右边的节点。

通过层序遍历可以得到每层节点的队列，索引[-1]即可得到每层最右边的节点。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        res = []
        que = [root]
        while que:
            res.append(que[-1].val)
            new_que = []
            for node in que:
                if node.left:
                    new_que.append(node.left)
                if node.right:
                    new_que.append(node.right)
            que = new_que
        return res

103. 二叉树的锯齿形层序遍历

奇偶层队列顺序不同的层序遍历，于是结合上面的BFS层序遍历方法，添加记录层数的变量，奇数层队列逆序。

自己写的，代码有点丑陋，之后有时间了再回来琢磨。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        res = []
        que = [root]
        cnt = 0
        while que:
            cur_res = [node.val for node in que]
            if cnt % 2 == 1:
                res.append(cur_res[::-1])
            else:
                res.append(cur_res)
            new_que = []
            for node in que:
                if node.left:
                    new_que.append(node.left)
                if node.right:
                    new_que.append(node.right)
            que = new_que
            cnt += 1
        return res

二叉搜索树

二叉搜素树的特点：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

二分搜索树遍历分为两大类，深度优先遍历和层序遍历。

深度优先遍历分为三种：先序遍历（preorder tree walk）、中序遍历（inorder tree walk）、后序遍历（postorder tree walk），分别为：

• **1、前序遍历：**先访问当前节点，再依次递归访问左右子树。
• 2、中序遍历：先递归访问左子树，再访问自身，再递归访问右子树。
• 3、后序遍历：先递归访问左右子树，再访问自身节点。

其中，中序遍历得到的数组为递增有序数组。

98. 验证二叉搜索树

可用DFS子树递归，因为判断是否为二叉搜索树，就是不断递归判断节点处是否满足二叉搜索树、且左右子树是否为二叉搜索树。

二叉搜索树的特点可转化为，每个节点都满足一个区间，每个节点的值是左子节点的上限、是右子节点的下限，根节点的区间可视为正无穷到负无穷。

1. 递的主体：左子树和更新后的区间上限self.isValidBST(root.left,left,value)、右子树和更新后的区间下限self.isValidBST(root.right,value,right)
2. 递的判断：二叉搜索树：左子树为二叉搜索树、右子树为二叉搜索树、本节点值在区间内
3. 归的边界条件：访问到空节点(返回true)

这个方法是前序遍历的。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root, left=-float("inf"), right=float("inf")):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root is None:
            return True
        value = root.val
        return left < value < right and self.isValidBST(root.left,left,value) and self.isValidBST(root.right,value,right)

99. 恢复二叉搜索树

根据二叉搜索树中序遍历后得到有序数组的特点：

1. 中序遍历得到数组

2. 找出并交换违背有序的节点

   恰好两个节点违背有序，pre/cur 型双指针搜索违背pre < cur的错误，记录第一次错误的pre值、第二次错误的cur值

class Solution(object):      
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        # 中序遍历得到数组
        nodes = []   
        def inorder(root, nodes):
            if not root:
                return
            inorder(root.left, nodes)
            nodes.append(root)
            inorder(root.right, nodes)
        inorder(root, nodes)
        # 找出并交换违背有序的节点
        big, small = None, None
        pre = nodes[0]
        for i in range(1,len(nodes)):
            if pre.val>nodes[i].val:
                small = nodes[i]
                if not big:
                    big = pre
            pre = nodes[i]
        if big and small:
            big.val,small.val = small.val,big.val
 
## if <变量> 
## if <变量> == None