翻转二叉树
题目:翻转一棵二叉树。
思路：这道题怎么说呢，审完题第一反应递归，迭代。我觉得类似于树，链表等差不多都是这个套路。至于细节我再慢慢看。
简单递归实现，贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)
return null;
//右树提出来赋值给左节点,递归实现，直到没有子树
TreeNode right = invertTree(root.right);
//左树提出来，赋值给右节点，同上
TreeNode left = invertTree(root.left);
root.left = right;
root.right = left;
return root;
}
}
还有一种迭代的方式，就是用到Queue队列，不过我真的对自己绝望了，上次看了一个类似的做法，但是自己写还是很懵，看了官方题解的代码才勉强用迭代实现了这个反转的功能：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)
return null;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
//知道栈空了才停止循环
while(!queue.isEmpty()){
//弹出第一层，并将第一层左右节点互换
TreeNode current = queue.poll();
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;
//把下一层元素放到队列中，如果左右都没有下一层元素了则队列就空了，也就退出循环了
if(current.right!=null){
queue.add(current.right);
}
if(current.left!=null){
queue.add(current.left);
}
}
return root;
}
}
2的幂
题目：给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1
输出: true
解释: 20 = 1
示例 2:
输入: 16
输出: true
解释: 24 = 16
示例 3:
输入: 218
输出: false
思路：一道送分题，简单粗暴，没什么好说的。直接贴代码：
class Solution {
public boolean isPowerOfTwo(int n) {
//第一遍提交测试案例是0，所以提出来了，以防万一写的<=
if(n<=0) return false;
while(n!=1){
//有余数说明奇数，肯定不是2的幂次方
if(n%2==1){
return false;
}
n /= 2;
}
return true;
}
}
用栈实现队列
题目：使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
思路：昨天才做了一个用队列实现栈，今天就用栈实现队列了。其实两者最大的区别也就是先入先出和先入后出的区别。我去撸代码了。昨天那道题的逆向思维就ok了。
这里还是简单介绍一个java中的栈Stack吧，也当复习了。
因为这个Stack直接就是实现类，所以也不用瞎寻思实例化哪个了，咱们来看看Stack的方法：
简单粗暴的就这么几个，题目要求push，pop，peek，empty是可以用的，也就够了，接下来再说这个题怎么做吧。我个人倾向于还是把push做改动，别的方法都照样用就行了。正好今天没什么事，我画个图来表示二者的区别和如何互相转化：
如图上所言，只要每次push 的时候把这个数列翻转过来，那么先入先出就会转成先入后出。先入后出就会转成先入先出。
昨天那道题用队列表示栈就是这么做的，今天这道用栈表示队列依然可以这样,直接上代码：
class MyQueue {
private Stack<Integer> stack;
/** Initialize your data structure here. */
public MyQueue() {
stack = new Stack<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
//为了保存这个元素之前的元素顺序
int[] arr = new int[stack.size()];
for(int i=0;i<arr.length;i++){
arr[i] = stack.pop();
}
//现在栈中是空的，把最新的元素push进去，这个元素就在最里面了
stack.push(x);
//再把之前顺序对的元素还原
for(int j =arr.length-1;j>=0;j--){
stack.push(arr[j]);
}
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
return (int)stack.pop();
}
/** Get the front element. */
public int peek() {
return (int)stack.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stack.empty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
至此问题解决。其实我这块按照昨天一样一样的逻辑写了一遍，但是有点坑，毕竟二者还是略微不同的，然后中间也一次次测试最终才形成完整版。
再说句心得：做题的时候千万不要急躁。因为每天我给自己定了任务，有时候时间很晚感觉完不成了开始着急，越是这样越没思路，看什么都不会。但是有时候心态好了慢慢做，哪怕比较浪费时间但是稳得一批，很多觉得比较难得也能做出来。好了，啰嗦几句，下一题！
回文链表
题目：请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路：我现在觉得进阶才是题目。。是不是飘了？哈哈。其实说真的，不考虑进阶要求简直就是一个送分题，遍历存数组，判断数组是不是回文就ok了。所以我直接把进阶当必须要求考虑了。我想起一个知识点。前几天做判断一个数组是否有单数元素的时候用过。计算，相同数字会为0.整个链表都是回文则最后遍历^一遍，结果应该是0。没毛病吧？我去撸代码试试。
有点问题，这个题目，如果只有中间一个单元素也算是true的。而且我刚刚也没考虑顺序问题，哎，这知识啊，都学杂了。还是换个思路吧。
我还是先用最low的一种方法实现了，然后在写的时候有了一个新思路：咱们一直说的回文，不就是从后往前和从前往后一样么？我是不是可以重新建立一个链表，反向向上挂节点，最后如果新链表和原链表一样就是回文的？
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<Integer>();
while(head!=null){
list.add(head.val);
head = head.next;
}
for(int i = 0 ;i<list.size()/2;i++){
if(!list.get(i).equals(list.get(list.size()-1-i))){
return false;
}
}
return true;
}
}
最low的实现，但是起码写了，就贴上来了。接下来按照刚刚的思路写一遍：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null) return true;
ListNode temp = new ListNode(head.val);
ListNode curr = head;
ListNode cur = temp;
while(curr.next!=null){
curr = curr.next;
cur = new ListNode(curr.val);
cur.next =temp;
temp = cur;
}
while(head!=null){
if(head.val!=temp.val){
return false;
}
head = head.next;
temp = temp.next;
}
return true;
}
}
这个运行效率还凑合，2ms，超过一半的人。不过空间不是O（1）我也没办法。看了大佬的解题思路：非要空间O（1）的话，就是快慢指针，一个走一个元素，一个走两个元素。等两个元素的走到头了，一个元素这个正好是中间点。然后我们把中间点往后的元素全部倒转（这个时间复杂度都多少了），再从头开始比较，果断倒转后的和从头比较到中间点的都一样是回文链表，否则不是。贴个代码:
class Solution {
public boolean isPalindrome(ListNode head) {
// 要实现 O(n) 的时间复杂度和 O(1) 的空间复杂度，需要翻转后半部分
if (head == null || head.next == null) {
return true;
}
ListNode fast = head;
ListNode slow = head;
// 根据快慢指针，找到链表的中点
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow = reverse(slow.next);
while(slow != null) {
if (head.val != slow.val) {
return false;
}
head = head.next;
slow = slow.next;
}
return true;
}
private ListNode reverse(ListNode head){
// 递归到最后一个节点，返回新的新的头结点
if (head.next == null) {
return head;
}
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
然后这道题就这样吧，继续下一道。
二叉搜索树的最近公共先祖
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
思路：这个无论从题目标题还是正文都看上去很高大上的题，额，然后一次通过了？有点诧异啊？其实这个有个名词要特别注意：二叉搜索树。这就说明不是那些乱七八糟的数据了，要严格遵循左小右大的规律。基于这点判断给定的两个节点处于哪个分界节点就行了。直接上代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val>=root.val&&q.val<=root.val){
return root;
}
if(p.val<=root.val&&q.val>= root.val){
return root;
}
if(p.val<=root.val&&q.val<= root.val){
return lowestCommonAncestor(root.left,p,q);
}
if(p.val>=root.val&&q.val>= root.val){
return lowestCommonAncestor(root.right,p,q);
}
return null;
}
}
因为这个无论是性能还是消耗都很优秀，而且这个题目是真的简单，所以也不看题解了，下一道题吧。
删除链表中的节点
题目：请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
思路：这道理我要好好说一下，题目很费解，考的就是阅读理解。实际上给的demo只有一个参数是个ListNode类型，蒙了很久，一个个测试案例测试才明白。给的参数就是要删除的哪个节点。比如给的链表5-2-1。要把它变成2-1.而且没有返回值,必须在这个链表上操作.就是这么一个题..做起来不难,就是理解题目难.直接上代码吧,感觉都对不起审了那么久的题:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
就这样.本题完毕,两行代码.
然后今天就学到这里,如果稍微帮到你了记得点个喜欢点个关注.也祝大家工作顺顺利利!
