题目一
描述
有10个球和10个盒子，每次可以拿一个球或者两个球放入盒子之中。每个盒子只能装一个球，一共有多少种放法？
解答
题目和上楼梯问题是一个道理（每次可以上一个或者两个台阶），是一个斐波那契数列问题。有如下推导：1
2
3
4
5
6f(n) = f(n - 1) + f(n - 2);
f(1) = 1;
f(2) = 2;
=>
数列为：1 2 3 5 8 13 21 34 55 89
f(10) = 89;
题目二
描述
复制一颗二叉树，前提：不能使用递归。
解答
源码如下：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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105import java.util.ArrayList;
//二叉树的复制
public class BinaryTreeCopy {
public static void main(String[] args) {
new BinaryTreeCopy();
}
//初始化测试数据
public BinaryTreeCopy(){
/**
* 1
* 2 3
*
* 4
*/
BinaryTreeNode<Integer> fromTree = new BinaryTreeNode<Integer>();
fromTree.setData(1);
BinaryTreeNode<Integer> lchild = new BinaryTreeNode<Integer>();
lchild.setData(2);
BinaryTreeNode<Integer> rchild = new BinaryTreeNode<Integer>();
rchild.setData(3);
fromTree.setLchild(lchild);
fromTree.setRchild(rchild);
BinaryTreeNode<Integer> llchild = new BinaryTreeNode<Integer>();
llchild.setData(4);
lchild.setLchild(llchild);
System.out.println("复制之前：");
transePre(fromTree);
System.out.println("复制之后：");
transePre(levelCopy(fromTree));
}
//先序遍历
public <T> void transePre(BinaryTreeNode<T> root){
if(root != null){
System.out.println(root.getData());
transePre(root.getLchild());
transePre(root.getRchild());
}
}
//层次拷贝
public <T> BinaryTreeNode<T> levelCopy(BinaryTreeNode<T> fromTree){
ArrayList<BinaryTreeNode<T>> levelList = new ArrayList<BinaryTreeCopy.BinaryTreeNode<T>>();
ArrayList<BinaryTreeNode<T>> levelListCopy = new ArrayList<BinaryTreeCopy.BinaryTreeNode<T>>();
BinaryTreeNode<T> root = copyNode(fromTree);
levelList.add(fromTree);
levelListCopy.add(root);
int count = 0;
while(true){
if(count < levelList.size()){
BinaryTreeNode<T> node = levelList.get(count);
BinaryTreeNode<T> nodeCopy = levelListCopy.get(count);
if(node.hasLeftChild()){
levelList.add(node.getLchild());
nodeCopy.setLchild(copyNode(node.getLchild()));
levelListCopy.add(nodeCopy.getLchild());
}
if(node.hasRightChild()){
levelList.add(node.getRchild());
nodeCopy.setRchild(copyNode(node.getRchild()));
levelListCopy.add(nodeCopy.getRchild());
}
count ++;
}else{
break;
}
}
return root;
}
//复制一个节点
public <T> BinaryTreeNode<T> copyNode(BinaryTreeNode<T> node){
BinaryTreeNode<T> newNode = new BinaryTreeNode<T>();
newNode.setData(node.getData());
return newNode;
}
//二叉树结点定义
class BinaryTreeNode<T>{
private T data;
private BinaryTreeNode<T> lchild;
private BinaryTreeNode<T> rchild;
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BinaryTreeNode<T> getLchild() {
return lchild;
}
public void setLchild(BinaryTreeNode<T> lchild) {
this.lchild = lchild;
}
public BinaryTreeNode<T> getRchild() {
return rchild;
}
public void setRchild(BinaryTreeNode<T> rchild) {
this.rchild = rchild;
}
public boolean hasRightChild(){
return rchild != null;
}
public boolean hasLeftChild(){
return lchild != null;
}
}
}