Leetcode——中级部分——树和图部分——Python实现_leetcode python图算法

中序遍历二叉树

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3
 
输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

 

我的解答：

方法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 inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def recurse(node):
            if node != None:
                recurse(node.left)
                res.append(node.val)
                recurse(node.right)
        recurse(root)
        return res

方法2——迭代实现（主要会用到数据结构 stack）：

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        stack = []
        result = []
        node = root
        while node or (len(stack) > 0):
            if node != None:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                result.append(node.val)
                node = node.right
        return result

 

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

 

我的解答：

层次遍历采用队列实现。
相比于标准层次遍历，这里只是在result中加入templist时加了一步判断flag是否为负的步骤，如果为负，表示是偶数次遍历应该从右往左，将templist更新为逆序

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root == None:
            return []
        
        result = []
        queue = [root]
        flag = 1
        while queue:
            length = len(queue)
            tempList = []
            #下面是一层的结点的遍历
            for i in range(length):
                node = queue.pop(0)
                tempList.append(node.val)
                if node.left != None:
                    queue.append(node.left)
                if node.right != None:
                    queue.append(node.right)
            #判断是否为偶数层（flag），如果是就需要逆序tempList
            if flag == -1:
                tempList = tempList[::-1]
            result.append(tempList)
            flag = flag * (-1)
        return result

 

从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

 

我的解答：

前序遍历先访问根节点，因此前序遍历序列的第一个字母肯定就是根节点，即A是根节点；然后，由于中序遍历先访问左子树，再访问根节点，最后访问右子树，所以我们找到中序遍历中A的位置，然后A左边的字母就是左子树了，也就是CBD是根节点的左子树；同样的，得到EF为根节点的右子树。将前序遍历序列分成BCD和EF，分别对左子树和右子树应用同样的方法，递归下去，二叉树就成功构建好了。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if preorder == []:
            return None
        root = TreeNode(preorder[0]) #构建一个树对象
        i = inorder.index(root.val) #在中序遍历序列中找到根节点索引
        root.left = self.buildTree(preorder[1:1+i],inorder[:i])
        root.right = self.buildTree(preorder[1+i:],inorder[i+1:])
        return root

 

每个节点的右向指针

给定一个二叉树

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

说明:

• 你只能使用额外常数空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
• 你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。

示例:

给定完美二叉树，

     1
   /  \
  2    3
 / \  / \
4  5  6  7

调用你的函数后，该完美二叉树变为：

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

 

我的解答：

采用BFS遍历（层次遍历），每一层遍历后，遍历节点列表，列表中前一节点next指针指向后一节点。

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
 
class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        node = [root]
        while node:
            temp = []
            for i in node:
                if i != None:
                    if i.left != None:
                        temp.append(i.left)
                    if i.right != None:
                        temp.append(i.right)
            for index,nodeValue in enumerate(node[:-1]):
                nodeValue.next = node[index+1]
            node = temp

 

二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

 

我的解答：

层次遍历得到二叉搜索树每一个元素，进行排序（list的sort函数），返回第k小元素。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        #下面是层次遍历过程
        queue = [root]
        lyst = []
        while queue:
            node = queue.pop(0)
            lyst.append(node.val) #list保存每一个元素
            if node.left != None:
                queue.append(node.left)
            if node.right != None:
                queue.append(node.right)
        #下面是排序过程
        lyst.sort()
        #下面是返回第k小元素过程
        return lyst[k-1]

 

岛屿的个数

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
 
输出: 1

示例 2:

输入:
11000
11000
00100
00011
 
输出: 3

 

我的解答：

我们遍历矩阵的每一个点,对每个点都尝试进行一次深度优先搜索,如果搜索到1,就继续向它的四周搜索。同时我们每找到一个1,就将其标为0,这样就能把整个岛屿变成0。我们只要记录对矩阵遍历时能进入多少次搜索,就代表有多少个岛屿。

class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        #注意：这个题目里面每个数字都是字符！！！
        row = len(grid)
        if row == 0:
            return 0
        column = len(grid[0])
        if column == 0:
            return 0
        res = 0
        for i in range(row):
            for j in range(column):
                if grid[i][j] == '1':
                    res = res + 1 #岛屿数+1
                    self.DFS(grid,i,j) #保证这个岛屿所有连接的位置都置零
        return res
        
    #深度优先遍历（所有相连岛屿置零操作）    
    def DFS(self,grid,i,j):
        #注意：这里需要一个判断是否溢出边界的条件
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]):
            return
        if grid[i][j] == '1':
            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)

注意：这里列表中不是整数数字而是字符！！