题目： 56.删除链表中的重复结点，57. 二叉树的下一个节点， 58. 对称的二叉树， 59. 按之字形顺序打印二叉树， 60. 按二叉树打印成多行
56. 删除链表中的重复结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：用一个临时指针标记重复元素的前一个元素，用一个游标去寻找重复元素，直到走完相同元素之后，定位到的第一个不同元素，将之前的临时指针指向这个不同元素，即删除了中间的重复元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead){
ListNode first = new ListNode(-1);
first.next = pHead;
ListNode pre = first;
ListNode cur = pHead;
while(cur!=null && cur.next != null){
if(cur.val == cur.next.val){
int val = cur.val;
while(cur != null && cur.val == val) cur = cur.next;
pre.next = cur;
}
else {
pre = cur;
cur = cur.next;
}
}
return first.next;
}
}
57. 二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下该结点的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路： 1. 当该结点有右子树的时候，返回右子树的最左侧的叶子结点。 2. 当该结点没有右子树的时候，说明该结点为所在子树的最右侧，则下一个结点在祖先结点中，因此返回某个父结点，满足该父结离该结点最近，且该结点在父亲结点的左子树中。
解法一：if判断不合法输入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode){
if(pNode.right != null){
pNode = pNode.right;
while(pNode.left != null) pNode = pNode.left;
return pNode;
}
while(pNode.next !=null ){
if(pNode.next.left == pNode) return pNode.next;
pNode = pNode.next;
}
return null;
}
}
58. 对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路： 递归判断每棵子树的镜像位置是否相等。即根结点的左孩子要等于右孩子，左孩子的左孩子要等于右孩子的右孩子，左孩子的右孩子要等于右孩子的左孩子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot){
###### if(pRoot == null) return true;
return isSymmetrical(pRoot.left, pRoot.right);
}
boolean isSymmetrical(TreeNode left, TreeNode right){
if(left == null) return right == null;
if(right == null) return false;
if(left.val != right.val) return false;
return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left);
}
}
59. 按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路： 与逐层打印二叉树的思路类似，但是设置一个计数器，当到偶数层的时候倒叙存储即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
int count = 1;
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(pRoot == null) return res;
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
Stack<Integer> stack = new Stack<Integer>();
queue.add(pRoot);
while(!queue.isEmpty()){
int len = queue.size();
ArrayList<Integer> layer = new ArrayList<Integer>();
for(int i = 0; i < len; i++){
TreeNode tmp = queue.remove(0);
if(tmp.left!=null) queue.add(tmp.left);
if(tmp.right!=null) queue.add(tmp.right);
if(count % 2 == 1) layer.add(tmp.val);
else if(count % 2 == 0){
stack.push(tmp.val);
}
}
if(count % 2 == 0){
while(!stack.isEmpty()) layer.add(stack.pop());
}
res.add(layer);
count++;
}
return res;
}
}
60. 按二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路： 将每个结点存入队列，一层一层输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.ArrayList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(pRoot == null) return res;
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
queue.add(pRoot);
while(!queue.isEmpty()){
int len = queue.size();
ArrayList<Integer> layer = new ArrayList<Integer>();
for(int i = 0; i < len; i++){
TreeNode tmp = queue.remove(0);
layer.add(tmp.val);
if(tmp.left != null) queue.add(tmp.left);
if(tmp.right != null) queue.add(tmp.right);
}
res.add(layer);
}
return res;
}
}