LeetCode 刷题总结（三）， 使用Python 实现。该篇题目类型主要包括：recursion, iteration 和dynamic programming。

** Regular Expression Matching**

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ' * ' . ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.

Tips：典型的dp，二维数组是常见的方式。

如果看不懂注释，可以看这里

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution(object):
    """
    dp, dp[i][j] means the match status between p[:i] and s[:j]
    """
    def isMatch(self, s, p):

        dp =[[False]*(len(s)+1) for _ in range(len(p) +1)]

        dp[0][0]= True
        
        # case, of when s is an empty string but p is not,
        # since each * can eliminate character before it
        for i in range(2, len(p)+1):
            dp[i][0] =dp[i-2][0] and p[i-1] =="*"

        for i in range(1, len(p)+1):
            for j in range(1, len(s)+1):
                if p[i-1] =='*':
                    # elimination or propagations
                    dp[i][j] =dp[i-2][j] or dp[i-1][j]
                    
                    #  another case, propagations
                    if p[i-2] ==s[j-1] or p[i-2] =='.':
                        # 下面两种写法都是可以
                        # dp[i][j] = dp[i][j] or dp[i][j-1]
                        dp[i][j] |= dp[i][j-1]
                        
                else:
                    # 对于and 这个语句就类似 if 语句, 下面两种写法都是可以的
                    #dp[i][j] =dp[i-1][j-1] and (p[i-1] ==s[j-1] or p[i-1] =='.')
                    
                    if p[i-1] ==s[j-1] or p[i-1] =='.':
                        dp[i][j] =dp[i-1][j-1]
        
        return dp[-1][-1]

Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’. ‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence).

使用动态规划的思想求解，那么思路就很明确。状态表示，转移方程和初始化。 使用 $f(i, j)$ 表示 s串的前 i 与 p 串的前 j 个字符是否匹配。（为了方便算法书写，下标都是从 1开始）。那么状态转移方程是

1
2

f(i, j) = f(i, j) | f(i -1, j -1) 当且仅当 x ==y 或者 y =='?'
f(i, j) = f(i, j) | f(i -1, j) | f(i, j -1) 当且仅当 y =="*"

初始化 f[0][0] =true, 那么 f[m][n] 就是最后的结果。

使用动态规划解该道题目的时候，发现 c++ 要比 python 简洁一些。以下结论：当使用基础算法的时候， c++ 明显是要好于 python ，当dfs 这些比较难的时候，python 可能更加合适，因为有库函数，比较简单的写法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    bool isMatch(string s, string p) {
        int n =s.size(), m =p.size() ;
        vector<vector<bool>> f(n +1, vector(m +1, false));
        f[0][0] =true;
        for(int i =0; i<=n ; i++)
            for(int j =1; j <=m ; j++)
            {
                char y =p[j-1];
                if (i >0)
                {
                    char x =s[i-1];
                    if(x ==y || y =='?')
                        f[i][j] =f[i][j] | f[i-1][j -1];
                }
                
                if( y =='*')
                {
                    f[i][j] = f[i][j] | f[i][j-1];
                    if( i >0)
                        f[i][j] = f[i][j] | f[i-1][j];
                }
            }
        return f[n][m];
    }
};

** Valid Parentheses**

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

Tips: 必须要使用 len(stack) 进行检测，因为中间的时候也可能 len(stack) 是等于0的，这时候只能是 append() ，不能访问 stack[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(object):

    def isMatch(self, l, r):

        return l =='[' and r==']' or l =='(' and r ==')' or l =='{' and r =='}'

    def isValid(self, s):

        len_s =len(s)
        if len_s ==0:
            return True

        stack =[]
        for ch in s:

            if len(stack) ==0 or not self.isMatch(stack[-1], ch):
                stack.append(ch)
            else:
                stack.pop()
        
        return len(stack) ==0

** Generate Parentheses**

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

讲解看c++ 中的讲解，需要注意的是在python 中加上了self 关键字，那么就是 ‘instance of class’，所以在之后的 solve函数中是可以直接使用的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def generateParenthesis(self, _n: int) -> List[str]:
        self.res =[] 
        if _n ==0: return []
        self.n = _n
        self.solve(0, 0, "")
        return self.res
    
    def solve(self,l, r , path):
        if(l ==self.n and r ==self.n):
            self.res.append(path)
        if l < self.n:
            self.solve(l +1, r , path +'(')
        if r < l:
            self.solve(l, r +1, path+ ')')

c++ 实现。 时间复杂度分析： 时间复杂度就是答案的个数 乘以保存答案 $O(n)$的计算量，即如下所示。 \begin{equation} O\left(\frac{n}{n+1} C_{2 n}^{n}\right)=O\left(C_{2 n}^{n}\right) \end{equation}

解题思路： 使用递归，可以放左括号的条件是当前左括号的数目不超过 $n$；放右括号的条件是当前右括号的数目不超过左括号。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<string> res;
    int n;
    void solve(int l, int r, string cur)
    {
        if(l ==n && r ==n)
        {
            res.push_back(cur);
            return ;
        }
        if(l <n)
            solve(l +1, r, cur +'(');
        if (r < l)
            solve(l , r +1,cur + ')');
    }
    vector<string> generateParenthesis(int _n) {
        if(_n ==0)
            return res;
        n = _n;
        solve(0, 0, "");
        return res;
    }
};

** Permutations**

Given a collection of distinct integers, return all possible permutations.

Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

Tips : extend 是因为list of list ，而不是单独的list，这样能保证最后的结果还是 list of list

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(object):
    def permute(self, nums):
        return self.doPermute(nums)

    def doPermute(self, num_list):
        if len(num_list) ==1:
            return  [num_list]
        
        res_list =[]
        for i in range(len(num_list)):
            num_list[0], num_list[i] =num_list[i], num_list[0]
            
            sub_list =self.doPermute(num_list[1:])
            list_head =[num_list[0]]
            #new_list =list_head+ sub_list
            new_list = [list_head + list1 for list1 in sub_list]
            # 可以理解这个是 sub_list 是有一系列的解， 然后再每个解上都加上一个头元素
            res_list.extend(new_list)
            # extend，The list.extend method extends a list by appending elements from an iterable
            # append 是当做一个整体进行操作
        return res_list

** Permutations II**

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Tips： 这个 duplicates 是通过 sort 函数，然后在选择 某个index 时候，进行判断一下是否和第一个重合，这样的方式去handle。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution(object):

    def doPermuteUnique(self, nums):
        
        if len(nums) ==1:
            return [nums]
        
        res_list =[]
        for i in range(len(nums)):
            
            if i>0 and nums[0] ==nums[i]:
                continue
            
            nums[0], nums[i] =nums[i], nums[0]
            sub_list =self.doPermuteUnique(nums[1:])
            list_head =[nums[0]]
            new_list =[list_head +list1 for list1 in sub_list]
            res_list.extend(new_list)
        return res_list
    
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        return self.doPermuteUnique(nums)

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer.

Tips： 数学题，斐波那契数列。

解法一：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution(object):
    # 可以换成数学模型，发现就是 斐波那契数列
    # 不使用数字，使用三个变量也是可以的额

    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n ==1:
            return 1
        elif n ==2:
            return 2
        
        arr = [0] *(n+1)
        arr[1] =1
        arr[2] =2
        
        for i in range(3, n+1):
            arr[i] =arr[i-1] +arr[i-2]
        
        return arr[n]

解法二，时间复杂度是$O(n)$,空间复杂度是$O(1)$，空间能够优化成$O(1)$的原因在于，转换方程只依赖于前两个的状态。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def climbStairs(self, n: int) -> int:
        if n==1: return 1
        if n==2: return 2
        a, b =1,2 
        c =0
        for i in range(3, n+1):
            c =a +b # 本次迭代的结果
            a, b =b, c # 为下一步做准备
        return c

使用递归的解法在LeetCode上会超时。

1
2
3
4
5
6
7
8
9

class Solution:
    def climbStairs(self, n: int) -> int:
        return self.dfs(n)
    
    def dfs(self, n):
        if n <=0 : return 0
        if n ==1: return 1
        if n ==2 : return 2
        return self.dfs(n-1) +self.dfs(n-2)

c++ 解法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int climbStairs(int n) {
        // 在想 为什么是dp， 而不是dfs。如果从结果上看，当然是可以认为其中有重复的计算单元，那么一般使用dp，而不是dfs。以你为dfs 是会超时的
        if(n ==1 || n ==2) return n;
        //return climbStairs(n -1) + climbStairs(n -2);
        int a =1, b =2;
        int c =0;
        for(int i =3; i<=n; i++)
        {
            c = a+b;
            a =b;
            b =c;
        }
        return b;
        
    }
};

** Combinations**

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Tips： 这个是处理的list 和 dfs()的问题，然后使用的传入 index和完整的 list 来控制进度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
    """
    好好理解递归这种逐渐加深的层次
    """
    def combine(self, n, k):

        res =[]
        self.dfs(list(range(1, n+1)), k, 0, [], res)

        return  res

    def dfs(self, nums, k, index, path, res):
        # backtracking
        #if k <0:
            #return
        # 这种 return 和result 结合使用的操作是经常常见的
        if k ==0:
            res.append(path)
            return
        # 这个index 是很重要的， 在这个index 的基础上选择的
        for i in range(index, len(nums)):
            self.dfs(nums, k-1, i +1, path+ [nums[i]], res)

** Subsets**

Given a set of distinct integers, nums, return all possible subsets (the power set).

Tips: 使用的是第二种方式，传入部分list，从而由大问题转移成小问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution(object):
    # 这种是最简单的深度优先的搜索了，
    def subsets(self, nums):
        
        res =[]
        self.dfs(nums, [], res)
        return res
    
    def dfs(self, nums, path, res):
        # 一般来说这个是有跳出条件，回溯的，但是这种情况是没有的，只有最后一个
        # [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]， 当输出 [1, 2,3] 的时候，return，但是这个return 到了 [1, 3] 这个层次
        res.append(path)
        
        for i in range(len(nums)):
            self.dfs(nums[i+1:], path+[nums[i]], res)

** Subsets II**

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Tips： 这个含有duplicates，使用功能sort 然后在 for 循环 的时候进行判断一下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution(object):
    # 递归
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        res =[]
        nums.sort()
        self.dfs(nums, 0, [], res)

        return res

    def dfs(self, nums, index, path, res):
        if  path not in res:
            res.append(path)

        #res.append(path)
        for i in range(index, len(nums)):
            if i > index and nums[i] ==nums[i-1]:
                continue
            self.dfs(nums, i+1, path+[nums[i]], res)
    # 下面的代码是错误的 memory 但是不知道为什么

** Decode Ways**

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Tips： 多少种解码方式。本质是裴波拉契数列, 感觉自己并没有get 到这个本质上是 该数列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution(object):
    """
    DP[i] = DP[i-1]   +   DP[i-2]
           \                  \___________(if   str[i-2] exists and 10<= int(str[i-1] + str[i]))<=26  )
             \___________(If str[i-1] exists and str[i] != '0' )
    """
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        if s =='10':
            return 1
        dp =[0] *(len(s) +1)
        dp[0] =1
        for i in range(1, len(s)+1):

            if s[i-1] !='0':
                dp[i] +=dp[i-1]

            if i >1 and '10' <=s[i-2:i] <='26':
                dp[i] += dp[i-2]

        return dp[-1]

** Binary Tree Inorder Traversal**

Given a binary tree, return the inorder traversal of its nodes' values.

Tips： 递归。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

class Solution(object):
    # inorder 中序遍历, recursive 递归， iterative 迭代
    
    # 这个是递归的 recursively 
    def helper(self, root, res):
        
        if root:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)

Tips： 递归的容易写，循环的也好会，使用的stack 先保存左子树，然后不断的node 其右子树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    def inorderTraversal(self, root):
        
        # 如果使用 迭代，那么就是 stack结构了
        res, stack =[], []
        
        while True:
            while root:
                stack.append(root)
                root =root.left
            
            if not stack:
                return  res
            
            node =stack.pop()
            res.append(node.val)
            root =node.right

** Validate Binary Search Tree**

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Tips： 二叉搜索树的特点，中序遍历，先得到遍历结果，然后判断是否是不减的（只是需要O(N)）.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        output =[]
        self.inOrder(root, output)
        
        for i in range(1, len(output)):
            if output[i-1] >= output[i]:
                return False
            
        return True
    
    def inOrder(self, root, output):
        
        if not root:
            return 
        self.inOrder(root.left, output)
        
        output.append(root.val)
        
        self.inOrder(root.right, output)

** Same Tree**

Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Tips: 对应的值相同，对应的结构相同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

class Solution(object):
    # 根据上一一个题目的要求，这个是也是可以先进行遍历，然后再比较最后的遍历结果吗
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        
        if not p and not q:
            return True
        
        elif not p or not q:
            return False
        
        if p.val ==q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False

** Symmetric Tree**

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Tip： 对称和 same 是在于比较的方式是不一样的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

class Solution(object):
    # 该题目和 isSameTree 是有点相似的，只是修改部分代码就可以 
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 这个如果是 [] 或者 None， 是返回true， 因为输入的形式是 list ，所以判断条件是 if root ==[], 这样形式
        if not root:
            return True

        return self.dfs(root.left, root.right)

    def dfs(self, p, q):

        if not p and not q:
            return True

        elif not p or not q:
            return  False

        if p.val == q.val:
            return self.dfs(p.left, q.right) and self.dfs(p.right, q.left)
        else:
            return False

** Binary Tree Zigzag Level Order Traversal**

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7], 3 /
9 20 /
15 7 结果是这样的： [ [3], [20,9], [15,7] ]

Tips： 一行是从左往右，一行是从右往左。层序遍历的变体。从左向右使用 append() ，然后从右向左使用 insert()，这个是没有问题的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

class Solution(object):
    #  层次遍历 + 奇偶性来决定是否 reverse
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(root, 0, res)
        return res

    def dfs(self, root, level, res):
        if root:
            if len(res) < level + 1:
                res.append([])
            if level % 2 == 0:
                res[level].append(root.val)
            else:
                res[level].insert(0, root.val)
            self.dfs(root.left, level+1, res)
            self.dfs(root.right, level+1, res)

LeetCode 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children.

Tips: 左右子树的max+1，这个是树的深度。时间复杂度是 $O(n)$， $n$ 表示结点的个数。

1
2
3
4
5
6
7
8
9

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) +1 if root else 0

c++ 实现，c++ 实现的代码在 if else 判断中没有python写法直观。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root ? max(maxDepth(root->left), maxDepth(root->right)) +1 :0;
    }
};

** Binary Tree Level Order Traversal II**

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

Tips: 层序遍历，但是 res 需要存储成list of list，这样最后进行reverse，能够表示出 层数的信息。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

class Solution(object):
    # 需要有一个 level的index， 然后翻转就行了
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res =[]
        self.dfs(root, 0, res)
        #res 这个是整体的导致，一层 element的倒置，不涉及 element内部的倒置
        return res[::-1]
    def dfs(self, root, level, res):
        
        if root:
            if len(res) < level+1:
                res.append([])
                # 这个是append 一个空的 [] 这种结构，然后下面使用该 list；否则的话 直接进行append 
            
            res[level].append(root.val) # 这个很重要哦
            
            self.dfs(root.left, level+1, res)
            self.dfs(root.right, level +1, res)

** Convert Sorted Array to Binary Search Tree **

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Tips： 不减的array 就是 binary search tree 中的中序遍历的结果。递归思想，先要找到 root，然后划分左右子树。递归进行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

class Solution(object):
    # balance tree 这种是递归进行定义的，左右子树相差最多为1
    # 主要是不太清楚 如何保证这种 balanced tree
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        
        if not nums:
            return  None
        
        mid =len(nums)//2
        root =TreeNode(nums[mid])
        
        root.left =self.sortedArrayToBST(nums[:mid])
        root.right =self.sortedArrayToBST(nums[mid+1:])
        
        return root

** Balanced Binary Tree**

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Tip：左右子树的差值不能大于1 为balanced，这个盘别题目，比较容易，重点是 getHeight() 的实现、根节点是 balanced，左右子树也是balanced

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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


class Solution(object):
    # 使用了之前的 求解 树的height 的东西，然后使用定义进行做题
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if not root:
            return True
        
        return abs(self.getHeight(root.left) -self.getHeight(root.right))<2 and self.isBalanced(root.left) and self.isBalanced(root.right)
    
    def getHeight(self, root):
        
        if not root:
            return 0
        return 1 +max(self.getHeight(root.left), self.getHeight(root.right))

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children.

Tip：求 height的变形，如果是叶子节点，那么返回 1+max(left, right) 否则的话，返回左右子树中较小的高度。如果是求高度，那么就不管了什么情况下都是返回 max()+1 .

对于求解高度或者最小高度的题目，一定要有叶子结点的相反，如果都不是叶子节点，那么不断求解最小。否则求解最大（向着另一边进行延伸生长）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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

class Solution(object):
    # 时间复杂度在O(n) 时间内，
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root: return 0
        if root.left and root.right:
            return min(self.minDepth(root.left) , self.minDepth(root.right)) +1
        else:
            return max(self.minDepth(root.left), self.minDepth(root.right)) +1

在c++ 中，整数之间直接使用 == 进行比较，对于浮点数，使用 abs(a-b) 进行比较。

** Path Sum**

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children.

Tips: 有条件的dfs(), 有条件的进行树的路径，树在加深的同时，target 数字也是不断的减少，最后如果相等，那么就是一个合适的解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

class Solution(object):
    #   树的路径
    # 总结一下 any all 这种到自己的博客
    """
    any:
    Returns true if any of the items is True. It returns False if empty or all are false. Any can be thought of as a sequence of OR operations on the provided iterables.
    all:
    Returns true if all of the items are True (or if the iterable is empty). All can be thought of as a sequence of AND operations on the provided iterables. It also short circuit the execution i.e. stop the execution as soon as the result is known.
    
    """
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        res =[]
        self.dfs(root, sum, res)
        return any(res)

    def dfs(self, root, target, res):
        if not root:
            return False
        
        # 对于叶子结点的定义
        if not root.left and not root.right:
            if root.val == target:
                res.append(True)
        if root.left:
            self.dfs(root.left, target-root.val, res)
        
        if root.right:
            self.dfs(root.right, target-root.val, res)

** Path Sum II**

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children.

Tips： 这个和上面的区别在于，一个是 true or false，一个find all paths，所以需要有一个变量去存储正确的路径。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

class Solution(object):
    # 上一道题目是 return true or false，这个是找到所有的路径
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        res =[]
        self.dfs(root, sum, [], res)
        return res
            
    def dfs(self, root, target, path, res):
        if not root:
            return []
        if not root.left and not root.right:
            if root.val == target:
                res.append(path+[root.val])
            
        if root.left: #这种条件是可以减少迭代的次数
            self.dfs(root.left, target-root.val, path+[root.val], res)
        
        if root.right:
            self.dfs(root.right, target-root.val, path+[root.val], res)

** Flatten Binary Tree to Linked List**

Given a binary tree, flatten it to a linked list in-place.

Tips： 比较有意思，将 tree 的左右子树 flatten 成 linked list的左右结点。其中的 self.pre 就类似一种全局变量，将整个遍历，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

class Solution(object):
    # 这种 flatten 就是 拉平（先序遍历）， 然后转成linkedlist
    # 并且这种操作是要求 in-place的
    def __init__(self):
        self.pre =TreeNode('dummy')
        
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """

        if not root:
            return 
        tmp =root.right # 这个保存下来，是为了下面的flatten 使用
        self.pre.right =root
        self.pre.left =None
        
        self.pre =root
        self.flatten(root.left)
        
        self.flatten(tmp)

** Populating Next Right Pointers in Each Node**

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

Tip，属于树的结构的优化，多了一个next 指针指向的是同层的右节点。这个树的操作一般是 in-place，所以在某个递归过程中 return 是不必return value，本生就是在修改。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, left, right, next):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution(object):
    # perfect binary tree, 
    # 题目的要求， populate each next pointer to its next right node

    def helper(self, left, right):
        if not left or not right:
            return
        
        left.next = right
        # 三种关系，先后顺序是没有关系的
        self.helper(left.left, left.right)
        self.helper(left.right, right.left)
        self.helper(right.left, right.right)
    
    def connect(self, root):
        if not root:
            return

        self.helper(root.left, root.right)
        
        return root

** Populating Next Right Pointers in Each Node II **

Given a binary tree struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Tips：注意从图片上观察这一题和上一题的区别，这图中表民一个子树的左子树是可以指向另一个子树的右子树，说明这个明显类似层次遍历，而不像上一题那样。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, left, right, next):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution(object):
    # 这个是不太明白的
    # 这个相对于上一道题目，只是少了 perfect binary tree, 翻译成中文，满二叉树（完美二叉树），包括最后一层都是满的
        
    def connect(self, root):
        if root is None:
                return None
        queue = [root]
        while queue:
            prev,curr = None,None
            size = len(queue)
            # 有点类似层次遍历的意思
            for i in range(size):
                curr = queue.pop(0)
                # 这个 if 只有在for 之内才是有效的，第一次是无效的
                if prev :
                    prev.next = curr
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
                prev = curr
            curr.next = None
        return root

Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Input: [-10,9,20,null,null,15,7] -10 /
9 20 /
15 7 Output: 42

Tips： 这个的难点在于，可以从任意点开始，然后再任意点结束，并且过不过根节点都是可以的。 分制到底部，在返回的时候传入左右任意一遍最大值加上目前root.val: cur = max(left, right) + root.val 这种情况处理了从Root到左右任意一边的最大值，也就是 root.val + left 和 root.val + right； 还有一种情况就是当最大值 = root.val + left + right， 我们在放入global变量的时候何其比较。 对于最底部叶子节点传上来的值，我们将其设置成0: return cur if cur > 0 else 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

class Solution:
    # 是可以从任意一节点出发，然后寻找最大值
    def maxPathSum(self, root: TreeNode) -> int:
        
        self.res =-float('inf')
        self.dfs(root)
        return self.res
    
    def dfs(self, root):
        
        if not root: return self.res
        
        left =self.dfs(root.left)
        right =self.dfs(root.right)
        self.res =max(self.res, left +right +root.val) # 和之前的res 相比较
        
        tmp =max(left, right) +root.val # 处理的是任意一边的最大值
        return tmp if tmp >0 else 0

** Sum Root to Leaf Numbers**

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. Note: A leaf is a node with no children.

Input: [1,2,3] 1 /
2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25.

Tips: 路径组成的数字代表一个数字，然后所有的路径和相加起来。关键代码只要 cur =pre*10 + root.val， 还是树的路径的遍历吧。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

class Solution(object):
    # 对于树的 类型，大概就是这样了， 递归，找出递归的跳出的条件，然后处理保存结果
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        
        self.result =0
        self.sumNum(root, 0)
        
        return self.result
    
    def sumNum(self, root, pre):
        
        if not root:
            return
        
        cur = pre *10 +root.val
        
        if not root.left and not root.right:
            self.result += cur
            return
        
        if  root.left:
            self.sumNum(root.left, cur)
        
        if root.right:
            self.sumNum(root.right, cur)

** Binary Tree Preorder Traversal**

Given a binary tree, return the preorder traversal of its nodes' values.

Tips：非递归版本（迭代），使用栈（递归的思想就是栈的思想）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

class Solution(object):
    # Recursive solution is trivial, could you do it iteratively?
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
    
        if not root:
            return []
        
        res, queue =[], [root]
        
        while queue:
            cur =queue.pop()
            if cur:
                res.append(cur.val)
                queue.append(cur.right)
                queue.append(cur.left)
                #queue.append(cur.right)
        
        return res

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. The cache is initialized with a positive capacity.

Tips：这个题目纯粹手解，太麻烦了，在python3 中有 collections.OrderedDict() 的实现，这是作弊的写法。特点在于dict +队列（不完全是队列，因为访问之后还会放到队列的最后，而不是弹出）。因为一般的dict 存储的时候是无序（不是按照放入的先后书序），ordereddict 是按照放入的先后顺序进行存储的。题目本身就是先进先出的队列，只不过存储的是 (key, value) 这样的键值对。使用get 的时候，get到一个不能删除，应该放到最后；put的时候在

OrderedDict.popitem()有一个可选参数last（默认为True），当last为True时它从OrderedDict中删除最后一个键值对并返回该键值对，当last为False时它从      OrderedDict中删除第一个键值对并返回该键值对。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class LRUCache(object):
    # python3 environment
    
    def __init__(self, capacity):
        self.size =capacity
        self.cache = collections.OrderedDict()

    def get(self, key):

        if key not in self.cache:
            return -1
        val =self.cache[key]
        self.cache.move_to_end(key) # Python >= 3.2
        
        return val

    def put(self, key, val):

        if key in self.cache:
            del self.cache[key]

        self.cache[key] =val

        if len(self.cache) > self.size:
            self.cache.popitem(last= False)
        
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

解法二：纯手写代码

key-value 的增删改查，需要使用hash 表来实现 关键是如何判断要删除的元素，使用双向链表实现 如果遇到新增的元素，那么加入到队尾，更新 hash表 如果遇到要删除的元素，那么删除队首的元素，更新hash 表b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

class Node(object):
    def __init__(self, key, x):
        self.key = key
        self.value = x
        self.next = None
        self.prev = None
    
class LRUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity    
        self.dic = {}
        self.head = None
        self.tail = None

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.dic:
            node = self.dic[key]
            self.makeMostRecent(node)
            return node.value
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key not in self.dic:
            # Invalidate oldest if required:
            if len(self.dic) == self.capacity:
                del self.dic[self.head.key]
                self.removeHead()
            node = Node(key, value)
            self.dic[key] = node
        else:
            # Update the value:
            node = self.dic[key]
            node.value = value
        self.makeMostRecent(node)
            
    def makeMostRecent(self, node):
        if self.head and self.head.key == node.key:
            self.removeHead()
        # Make this item the most recently accessed (tail):
        if self.tail and not self.tail.key == node.key:
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
            node.next = None
            self.tail.next = node  # Old tail's next is the node.
            node.prev = self.tail  # Node's previous is the old tail.
        self.tail = node  # New tail is the node.
        if not self.head:
            self.head = node  # If this is the first item make it the head as well as tail.
    
    def removeHead(self):
        self.head = self.head.next
        if self.head:
            self.head.prev = None

** Insertion Sort List **

Sort a linked list using insertion sort.

Tips： linkedlist 擅长于修改元素（直接修改指向），其中的 if while 是经常搭配使用，发现.. 然后就处理…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    # 前插
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p =dummy =ListNode(0)
        cur =dummy.next =head
        while cur and cur.next:
            next_val =cur.next.val

            if cur.val <= next_val:
                cur =cur.next
                continue
            # the sequence is not sorted inorder
            # find the proper situation
            # 从头开始找
            if p.next.val > next_val:
                p =dummy

            while p.next.val <= next_val:
                p =p.next

            p.next, cur.next.next, cur.next =cur.next, p.next, cur.next.next
        return dummy.next

** Sort List **

Sort a linked list in O(n log n) time using constant space complexity.

Input: 4->2->1->3
Output: 1->2->3->4

Tips: mergesort 的思想，显示把list 分成left and right（分），然后最后merge 算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    
    def merge(self, h1,h2):
        
        dummy =tail =ListNode(-1)
        
        while h1 and h2:
            if h1.val < h2.val:
                tail.next, h1 =h1, h1.next
            else:
                tail.next, h2 =h2, h2.next
            tail =tail.next
        tail.next =h1 or h2
        
        return dummy.next
    
    def sortList(self, head):
        
        if not head or not head.next:
            return head
        
        pre, slow, fast =None, head, head
        # slow fast 直接是两种快慢的不影响的index 遍历方式，slow 是下一个链表的结点
        while fast and fast.next:
            pre, slow, fast =slow, slow.next, fast.next.next
        
        pre.next =None
        # 下面的两种写法是等价的
        return self.merge(self.sortList(head), self.sortList(slow))
        # return self.merge(*map(self.sortList, (head, slow)))

Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Tips: 这个dfs 跟之前的不一样之处在于，需要对于每个点进行 dfs() ，其他的还好。提供了两种解法，第一种比较代码比较少。比较喜欢第一种代码的风格，这样两个函数看起来比较均衡。

https://leetcode.com/problems/number-of-islands/

解法一：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        if not grid:
            return 0

        count =0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] =='1':
                    self.dfs(grid, i,j) # 写法比较巧妙
                    count +=1
        
        return count
    
    def dfs(self, grid, i,j):
        
        if i <0 or j<0 or i>=len(grid) or j>= len(grid[0]) or grid[i][j] !='1':
            return 
        
        grid[i][j] ='0'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

解法二：两种思想一样，写法不一样。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        if not grid:
            return 0

        used =[ [False]* len(grid[0]) for _ in range(len(grid))]

        count =0

        for i in range(len(grid)):

            for j in range(len(grid[0])):

                num =self.dfs(grid, used, len(grid)-1, len(grid[0])-1, i, j)
                if num>0:
                    count +=1
        return count
    
    def dfs(self, grid, used, row, col, x, y):
        if grid[x][y] =='0' or used[x][y]:
            return  0
        used[x][y] =True
        
        num =1
        if x!=0:
            num += self.dfs(grid, used, row, col, x -1, y)
        
        if x !=row:
            num += self.dfs(grid, used, row, col, x +1,y)
        if y!=0:
            num += self.dfs(grid, used, row, col, x, y-1)
        if y !=col:
            num += self.dfs(grid, used, row, col, x, y+1)
            
        return num

** Super Egg Drop**

You are given K eggs, and you have access to a building with N floors from 1 to N. Each egg is identical in function, and if an egg breaks, you cannot drop it again. You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution(object):

    def gameOfLife(self, board):

        # 纯粹的count，之后的判断是下面决定的
        def count(x, y):
            res =0
            # 遍历 点的四周
            for r in range(x-1, x+2):
                for c in range(y-1, y+2):

                    if (r!= x or c!=y) and 0<= r < len(board) and 0<= c < len(board[0]) and board[r][c] >0:
                        res +=1
            return res

        for x in range(len(board)):
            for y in range(len(board[0])):
                board[x][y]  =count(x, y) +1 if board[x][y] ==1 else -count(x, y)
                # if board[x][y] == 1, change its value to count(x,y) + 1, the reason I add 1 is to keep it positive

        for x in range(len(board)):
            for y in range(len(board[0])):
                board[x][y] = 1 if board[x][y] in {3, 4, -3} else 0 # {2, 3, -3}

** Kth Smallest Element in a BST**

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Tips: 二分查找树，中序遍历就是不减的list .有递归，迭代两个版本，共三种实现。倾向于使用第二个版本。迭代，然后使用k 进行及时的跳出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

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

class Solution(object):
    # BST 中序遍历 得到一个不减的list，然后就可得第k 小的元素
    
    # 下面是递归版本
    '''

    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        if not root:
            return 
        res =[]
        self.dfs(root, res)

        
        if len(res) +1<k:
            return 
        return res[k-1]
        
    
    def dfs(self, root, res):
        
        if not root:
            return 
        #res.append(root.val)
        self.dfs(root.left, res)
        res.append(root.val)
        self.dfs(root.right, res)
        
    '''
    '''

    # 相比于第一种方式，时间上是有减少的
    def kthSmallest(self, root,k ):
        stack =[]
        node =root
        
        while True:
            if node:
                stack.append(node)
                node =node.left
            else:
                node =stack.pop()
                # 使用计数的方式进行访问，减少了空间复杂度
                k -=1
                if not k:
                    break
                node =node.right
        return node.val
    '''
    # 这个代码就是有点 抖机灵的那种，如果使用了 try ..catch.. 那么exception 就不会报错
    def kthSmallest(self, root, k):
        
        def inorder(root, k):
            if root:
                inorder(root.left, k)
                if k ==1:
                    raise Exception(root.val)
                inorder(root.right, k-1)
            #return k
        
        try:
            inorder(root, k)
        except Exception as e:
            return e.message

** Lowest Common Ancestor of a Binary Tree**

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Tips: 这道Follow Up没有BST的特性，所以要对几种case一个一个进行测试。Condition为两种：如果没找到，返回None，找到则返回当前的root(因为找到一个root就不需要继续深入)比对方式：

  • 如果parent的左右孩子都有返回，说明parent就是LCA
  • 如果左边没有返回：则右边返回的就是LCA
  • 如果右边没有返回：则左边返回的就是LCA

讲解

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

class Solution(object):

    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root: return  None
        if p ==root or q ==root:
            return root

        left =self.lowestCommonAncestor(root.left, p, q)
        right =self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        if not left:
            return right
        if not right:
            return left

** Serialize and Deserialize Binary Tree**

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Tips: 序列化主要是用在 存储和传输上吧. 基于 队列进行实现。队列可以两边进行修改。先序遍历

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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

class Codec:
    # 先序遍历
    def serialize(self, root):
        if not root: return ""
        queue =collections.deque([root])
        res =[]
        # 这个就是一种循环先序遍历二叉树
        while queue:
            # 使用 pop 和 append() 操作右边
            node =queue.popleft() # 在队列中使用 popleft 和appendleft() 直接操作队列的左边的增减
            if node:
                queue.append(node.left)
                queue.append(node.right)
            res.append(str(node.val) if node else '#') # 使用 # 表示是一种none
        return ','.join(res) # 使用, 隔开每个node
    
    def deserialize(self, data):
        
        if not data: return None
        nodes =data.split(',')
        
        root =TreeNode(int(nodes[0]))
        
        queue =collections.deque([root])
        
        index =1 # 作为string 的index
        while queue:
            node =queue.popleft()
            
            if nodes[index] != "#": # nodes[index] is not '#' 这样写也是可以的
                node.left =TreeNode(int(nodes[index]))
                queue.append(node.left)
            index +=1
            
            if nodes[index] != "#":
                node.right =TreeNode(int(nodes[index]))
                queue.append(node.right)
            index +=1
        return root
    
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

** Binary Tree Maximum Path Sum**

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Tips: 这个不是树的路径，可以从任意非根节点出发。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

class Solution(object):
    
    # 根据以往的经验，树的递归解法一般都是递归到叶节点，然后开始边处理边回溯到根节点。
    # 但是这个题目不是， 这个是可以任意 start， 任意 end，然后不一定要经过根节点
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 这种全局变量的设置确实是必须的，当携带变量的时候就出错了
        self.res = - float('inf')
        self.dfs(root)
        return self.res


    def dfs(self, root):
        if not root: return 0
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        self.res = max(self.res, left + right + root.val)
        cur = max(left, right) + root.val
        return cur if cur > 0 else 0

** Number of Islands**

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Tips: dfs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution(object):
    # dfs 是一个中规中矩的算法
    # 这种方式更加简洁一点，直接使用 grid[i][j] 是否等于1 进行操作，
    # 然后如果能返回，在主程序中进行计数，最后的结果比较nice
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        count =0
        for i in range(len(grid)):
            for j in range(len(grid[0])):

                if grid[i][j] =='1':
                    self.dfs(grid, i,j)
                    count +=1
        return count

    def dfs(self, grid, i, j):

        if i<0 or j<0 or i>=len(grid) or j >=len(grid[0]) or grid[i][j]!='1':
            return 
        grid[i][j] ='#'
        
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i,j +1)
        self.dfs(grid, i, j-1)

** Course Schedule **

There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Tips: dfs 先修课程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution(object):
    
    """
    这种解释是比较nice的，使用 0 -1 和1 分别表示初始化，正在访问和已经完成
    if node v has not been visited, then mark it as 0.
    if node v is being visited, then mark it as -1. If we find a vertex marked as -1 in DFS, then their is a ring.
    if node v has been visited, then mark it as 1. If a vertex was marked as 1, then no ring contains v or its successors.
    """
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
    
        graph = [[] for _ in range(numCourses)]
        visited = [0 for _ in range(numCourses)]
        # create graph
        for pair in prerequisites:
            x, y = pair
            graph[x].append(y)
        # visit each node
        for i in range(numCourses):
            if not self.dfs(graph, visited, i):
                return False
        return True
    
    def dfs(self, graph, visited, i):
        # if ith node is marked as being visited, then a cycle is found
        if visited[i] == -1:
            return False
        # if it is done visted, then do not visit again
        if visited[i] == 1:
            return True
        # mark as being visited
        visited[i] = -1
        # visit all the neighbours
        for j in graph[i]:
            if not self.dfs(graph, visited, j):
                return False
        # after visit all the neighbours, mark it as done visited
        visited[i] = 1
        return True

** Course Schedule II**

There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Tips: 和上一题相似，dfs 求解的是路径问题，而不是最值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution(object):
    # 上一题是true or false 这个题目要求给个能够完成的路径，哎
    # 不得不说这个是图的知识点呀
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        def dfs(i, visited, graph, res):
            if visited[i] ==1:
                return True

            if visited[i] ==-1:
                return False

            visited[i] =-1
            for n in graph[i]:
                if not dfs(n, visited, graph, res):
                    return False
            
            res.append(i)
            visited[i] =1
            return True
        
        visited =[0] * numCourses
        graph ={x :[] for x in range(numCourses)}
        
        #  注意这个顺序，因为最后要的是路径，所以这样是更加合理的
        for p in prerequisites:
            graph[p[1]].append(p[0])
        
        res =[]
        
        for i in range(numCourses):
            if not dfs(i, visited, graph, res):
                return []
        return res[::-1]