Code 1
Question
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2
Input: head = [1,2]
Output: [2,1]
Example 3
Input: head = []
Output: []
Solution
- 迭代
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
prev=None
while head :
next=head.next
head.next=prev
prev=head
head=next
return prev
在遍历链表时，将当前节点的 next \textit{next} next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next :
return head
p=self.reverseList(head.next)
head.next.next=head
head.next=None
return p
注意几点 ：
- 相当于从最后一个向前换
- 交换部分代码
head.next.next=head head.next=None p一直是最后一个节点
Code 2
Question
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).Implement the MyQueue class.
void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.
Notes
You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.
Example 1
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
Answer
- 使用两个栈
class MyQueue(object):
def __init__(self):
self.stack1=[]
self.stack2=[]
self.front=None
def push(self, x):
if not self.stack1 :
self.front=x
while self.stack1 :
self.stack2.append(self.stack1.pop())
self.stack2.append(x)
while self.stack2 :
self.stack1.append(self.stack2.pop())
def pop(self):
p=self.stack1.pop()
if self.stack1 :
self.front=self.stack1[-1]
return p
def peek(self):
return self.front
def empty(self):
if self.stack1 :
return False
else :
return True
stack2主要用于反转列表
Code 3
Question
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Example 1
Input: root = [1,null,2,3]
Output: [1,2,3]
Example 2
Input: root = []
Output: []
Example 3
Input: root = [1]
Output: [1]
Example 4
Input: root = [1,2]
Output: [1,2]
Example 5
Input: root = [1,null,2]
Output: [1,2]
Answer
- 递归
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
l=[]
self.preorder(root,l)
return l
def preorder(self,root,l) :
if not root :
return
l.append(root.val)
self.preorder(root.left,l)
self.preorder(root.right,l)
- 迭代
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root :
return []
stack=[]
ans=[]
stack.append(root)
while stack :
p=stack.pop()
ans.append(p.val)
if p.right :
stack.append(p.right)
if p.left :
stack.append(p.left)
return ans
利用栈来解决，因为前序遍历是中->左->右，所以入栈顺序是右->左->中。
Code 4
Question
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
Example 1
Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2
Input: root = []
Output: []
Example 3
Input: root = [1]
Output: [1]
Example 4
Input: root = [1,2]
Output: [2,1]
Example 5
Input: root = [1,null,2]
Output: [2,1]
Answer
- 递归
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
l=[]
self.postorder(root,l)
return l
def postorder(self,root,l):
if not root :
return
self.postorder(root.left,l)
self.postorder(root.right,l)
l.append(root.val)
- 迭代
注意这里没看懂！！
Code 5
Question
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2
Input: root = [1,2,2,null,3,null,3]
Output: false
