2.2 该节点为父节点的右子节点,则沿着父节点向上遍历,直到找到一个节点,这个节点的left子树是给出节点的father节点。比如当前节点是D,则第一个满足的就是节点F,因为F节点的left节点是D节点的father节点。故D中序遍历的下一个节点就是F节点。 中序遍历如下:A - C - B - D - F - H - E - M - G
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。
def __init__(self): """ Initialize your data structure here. """ self.stackA = [] self.stackB = []
def push(self, x): """ Push element x to the back of queue. :type x: int :rtype: None """ while self.stackA: self.stackB.append(self.stackA.pop()) self.stackA.append(x) while self.stackB: self.stackA.append(self.stackB.pop())
def pop(self): """ Removes the element from in front of queue and returns that element. :rtype: int """ return self.stackA.pop()
def peek(self): """ Get the front element. :rtype: int """ return self.stackA[-1]
def empty(self): """ Returns whether the queue is empty. :rtype: bool """ return self.stackA == []
# Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()
用两个队列实现栈
题目描述 使用队列实现栈的下列操作:
push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空 注意:
你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
def __init__(self): """ Initialize your data structure here. """ from collections import deque self.q = deque()
def push(self, x): """ Push element x onto stack. :type x: int :rtype: None """ self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft())
def pop(self): """ Removes the element on top of the stack and returns that element. :rtype: int """ return self.q.popleft()
def top(self): """ Get the top element. :rtype: int """ return self.q[0]
def empty(self): """ Returns whether the stack is empty. :rtype: bool """ return not len(self.q)
# Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty()
class Solution(object): def myPow(self, x, n): """ :type x: float :type n: int :rtype: float """ if n == -1: return 1.0/x elif n == 0: return 1 elif n == 1: return x else: res = x tmp = Solution() if n % 2 == 1: res = tmp.myPow(x, n//2) ** 2 * x else: res = tmp.myPow(x, n//2) ** 2 return res
打印从1到最大的n位数
删除链表中的节点
描述 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 现有一个链表 – head = [4,5,1,9],它可以表示为:
def FindKthToTail(self, head, k): fast = slow = head for _ in range(k): if fast: fast = fast.next else: return None while fast: slow, fast = slow.next, fast.next return slow