剑指offer--day08

1.1 题目：二叉树镜像：操作给定的二叉树，将其变换为源二叉树的镜像。

1.2 思路：先交换根节点的两个子结点之后，我们注意到值为10、6的结点的子结点仍然保持不变，因此我们还需要交换这两个结点的左右子结点。做完这两次交换之后，我们已经遍历完所有的非叶结点。此时变换之后的树刚好就是原始树的镜像。交换示意图如下所示：

1.3 代码：

 # -*- coding:utf-8 -*-

 # class TreeNode:

 #     def __init__(self, x):

 #         self.val = x

 #         self.left = None

 #         self.right = None

 class Solution:

     # 返回镜像树的根节点

     def Mirror(self, root):

         # write code here

         if root == None:

             return False

         if root.left == None and root.right == None:

             return root

         temp = root.left

         root.left = root.right

         root.right = temp

         if root.left != None:

             self.Mirror(root.left)

         if root.right != None:

             self.Mirror(root.right)

2.1 题目：顺时针打印矩阵：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

2.2 思路：将结果存入vector数组，从左到右，再从上到下，再从右到左，最后从下到上遍历。

2.3 代码：

 # -*- coding:utf-8 -*-

 class Solution:

     # matrix类型为二维列表，需要返回列表

     def printMatrix(self, matrix):

         # write code here

         rows = len(matrix)

         cols = len(matrix[0])

         result = []

         if rows == 0 and cols == 0:

             return result

         left, right, top, buttom = 0, cols-1, 0, rows - 1

         while left <= right and top <= buttom:

             for i in range(left, right+1):

                 result.append(matrix[top][i])

             for i in range(top+1, buttom + 1):

                 result.append(matrix[i][right])

             if top != buttom:

                 for i in range(left, right)[::-1]:

                     result.append(matrix[buttom][i])

             if left != right:

                 for i in range(top+1, buttom)[::-1]:

                     result.append(matrix[i][left])

             left += 1

             top += 1

             right -= 1

             buttom -= 1

         return result

3.1 题目：包含min函数的栈：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

3.2 思路：使用两个stack，一个为数据栈，另一个为辅助栈。数据栈用于存储所有数据，辅助栈用于存储最小值。

　　举个例子：

　　入栈的时候：首先往空的数据栈里压入数字3，显然现在3是最小值，我们也把最小值压入辅助栈。接下来往数据栈里压入数字4。由于4大于之前的最小值，因此我们只要入数据栈，不压入辅助栈。

　　出栈的时候：当数据栈和辅助栈的栈顶元素相同的时候，辅助栈的栈顶元素出栈。否则，数据栈的栈顶元素出栈。

　　获得栈顶元素的时候：直接返回数据栈的栈顶元素。

　　栈最小元素：直接返回辅助栈的栈顶元素。

3.3 代码：

 # -*- coding:utf-8 -*-

 class Solution:

     def __init__(self):

         self.stack = []

         self.min_stack = []

     def push(self, node):

         # write code here

         self.stack.append(node)

         if not self.min_stack or node <= self.min_stack[-1]:

             self.min_stack.append(node)

     def pop(self):

         # write code here

         if self.stack[-1] == self.min_stack[-1]:

             self.min_stack.pop()

         self.stack.pop()

     def top(self):

         # write code here

         return self.stack[-1]

     def min(self):

         # write code here

         return self.min_stack[-1]

参考：https://cuijiahua.com/

巴特西

剑指offer--day08

最新文章

热门文章