Home

题目链接 此题与jz032II.从上到下打印二叉树II相同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] queue, res = [root], [] while queue: tmp = [] for _ in range(len(queue)): node = queue.pop(0) ...

题目链接 嗯，试了一下，大概知道是分治的思路，但是好像总写不对递归终止的条件，写得比较繁琐。简单来说，在后序遍历得到的序列中，最后一个数字是树的根节点的值，除了最后一个节点的前面的数字也可以分成两部分：前一部分是左子树节点的只，它们都比根节点的值小；第二部分是右节点的值，它们都比根节点的值大。知道了这个特性，我们就可以继续递归地判断应该在某个子树里的数字是否是一个合格的序列。终止条件一下子不好想，下面代码里呈现的是：遍历数组，当数组中出现第一个数字大于等于根节点（也就是序列末位）的值时，我们就认为这个时刻是从左子树过渡到右子树的时刻；当继续向序列末尾遍历时，当出现第一个数字小于等于（正常情况下应该是等于，因为第二部分当数字应该都严格小于根节点）根节点时，我们认为走到了末尾。这时候的下...

题目链接 额，我就是把jz032II在tmp里存好每一层的时候间隔着反转了一下数组然后加入了答案中。应该不是这样做的吧？额看了一下好像这种实现也还行，我就不来讨论别的解法了，因为看起来代码也没有更加简洁之类的。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def levelOrder(self, root: T...

题目链接 好的，按照bfs写了一下自己朴素的解法，就很简单了，不用多说了吧。当然别人还有更加好一点的实现，如解法2所示。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 class Solution: def levelOrder1(self, root: TreeNode) -> List[List[int]]: if not root: return [] queue, res = [root], [[root.val]] while queue: tmpnode = [] tmpval = [] for node...

题目链接 此题与jz031.栈的压入、弹出序列相同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 class Solution: def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: stack, i = [], 0 for num in pushed: stack.append(num) while stack and stack[-1] == popped[i]: stack.pop() i += 1 ...

题目链接 第一遍的时候写错了，直接写成先根序遍历了可还行。这题就是很典型的层序遍历而已，用一个队列记录每一层的节点，在遍历每层的时候将答案加到res里。我把jz055I.二叉树的深度这个题的代码拿来稍微改了一下就ok了。至于解法2，就是用时间换了一部分空间。这个算法的时间复杂度因为节点数量是N所以是O（N），空间复杂度是O（N），在最差情况下，即当树为平衡二叉树时，最多N/2 个树节点同时在 queue 中，所以为O（N）。 class Solution: def levelOrder1(self, root: TreeNode) -> List[int]: if not root: return [] que...

题目链接 解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。具体来说，算法1描述的思路就是，检查popped的每一个元素，如第一个元素，判断其是否在辅助栈中，若是，则将改元素弹出并检查poped中的下一个元素；若不是，则将pushed中的元素依此压入辅助栈中直到压入的数字与正在检查的元素相同时，弹出这个元素并检查下一个元素。当pushed中的所有元素都被压入辅助栈但poped中还有元素剩余时，返回False，或当popped已经遍历结束但pushed中还有元素剩余时，也返回False，反之返回True。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 不过我这个思想比较别扭，其实算法2就是比较正...

题目链接 此题与jz030.包含min函数的栈相同。 class MinStack: def __init__(self): """ initialize your data structure here. """ self.A, self.B = [], [] def push(self, x: int) -> None: self.A.append(x) if not self.B or x <= self.B[-1]: self.B.append(x) def pop(self) -> None: ...

题目链接 这个问题，难点在于min函数的设计，对于这个函数，我们的第一反应可能会是用一个元素存放最小的元素， 并在新元素被压入栈时更新变量，然后在调用min函数时将相应元素返回。但是，这种设计带来的问题就是，如果当前最小的元素被弹出栈了，那么如何得到下一个最小的元素？分析到这里我们会发现，仅仅用一个额外的成员变量来保存最小元素是不够的，那是否可以用一个辅助栈来保存每次最小的元素呢？算法1实现的就是这种思路。这个算法的时间复杂度是O（1），空间复杂度是O（N）。 但是，这个设计仍在辅助栈里保存了一些多余的元素，那就是不需要在每次元素入栈的时候在辅助栈中添加元素，只有当最小元素发生改变时才在辅助栈里加新元素。当调用min函数时，若mainStack中要弹出的元素是当前最小的元素的时候，...

题目链接 此题与jz027.二叉树的镜像相同。